SRM308 CornersGame

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

$6 \times 6$の盤面が与えられて，右下の$2 \times 2$にはコインが置いてある．最終的に左上$2 \times 2$に移動させたい．コインの移動は$2$種類ある．

  • 隣接したマスに障害物がなければ移動できる
  • 隣接したマスが石かコインでそれをジャンプした先に障害物がなければ移動できる

もし移動出来なければ$-1$，そうでなければ最小の移動回数を返す．

読み飛ばしていて死んでいた．ジャンプできるのは石だけだと思っていて，最初のサンプルが$16$になる理由が全くわからなかった．問題文を読みなおすと$top\ left$かつ正方形ならなんでも良いのかと思って，それを全探索したりしていた．
コインもジャンプ可能なので，順番に飛ばし飛ばしで行くとコストが少なくいける．(移動回数, 盤面)を状態として，移動回数が少ない順に見ていった．
Sample0

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, vector<string> > IS;

int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};

bool can(int y, int x) {
  if(0 <= y && y < 6 && 0 <= x && x < 6) return true;
  return false;
}


class CornersGame {
  public:
  int countMoves(vector <string> board) {
      int n = 6;
      vector<string> s = board;
      s[n-2][n-2] = 'X';
      s[n-2][n-1] = 'X';
      s[n-1][n-2] = 'X';
      s[n-1][n-1] = 'X';

      set<vector<string> > st;
      priority_queue<IS, vector<IS>, greater<IS> > que;
      que.push(mp(0, s));

      while(que.size()) {
          IS is = que.top(); que.pop();
          int cnt = is.first;
          s = is.second;

          if(s[0][0] == 'X' && s[0][1] == 'X' && s[1][0] == 'X' && s[1][1] == 'X') {
              return cnt;
          }

          rep(i, n) {
              rep(j, 6) {
                  if(s[i][j] != 'X') continue;

                  rep(k, 4) {
                      int y = i + dy[k];
                      int x = j + dx[k];

                      if(can(y, x) && s[y][x] == '.') {
                          vector<string> t = s;
                          swap(t[i][j], t[y][x]);
                          if(st.find(t) == st.end()) {
                              st.insert(t);
                              que.push(mp(cnt + 1, t));
                          }
                      }

                      int ny = y + dy[k];
                      int nx = x + dx[k];

                      if(can(y, x) && (s[y][x] == 's' || s[y][x] == 'X') && can(ny, nx) && s[ny][nx] == '.') {
                          vector<string> t = s;
                          swap(t[i][j], t[ny][nx]);
                          if(st.find(t) == st.end()) {
                              st.insert(t);
                              que.push(mp(cnt + 1, t));
                          }
                      }
                  }
              }
          }
      }

      return -1;
  }
};
Aug 31st, 2016
dijkstra, srm, topcoder