SRM 308 Div1 Medium CornersGame

問題

6x6のチェス盤があり、セルには石と旗の2種類の障害物がある。右下の4セルにコインが置かれており、これらのコインは隣接する空白のセルに移動できる。また、隣接するセルに別のコインが置いてある、もしくは石が置いてある場合で、更に隣のセルが開いている場合は隣接するセルを飛び越して空白セルに移動することができる。なお旗が置いてあるセルには移動できないし、旗を飛び越すこともできないものとする。
4枚のコインを左上に移動するために必要な最小の移動回数を求めよ。ただし4枚のコインは互いを区別しないものとする。

やりかた

コインの全配置パターンはせいぜい36C4 ≒ 60000なので盤面の各パターンを状態として初期状態からゴールまでの幅優先探索で答えを求めることができる。

以下ソース。

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

class CornersGame {
public:
  bool goal(vector<string> m){
    return m[0][0] == 'd' && m[0][1] == 'd' && m[1][0] == 'd' && m[1][1] == 'd';
  }
  bool in(int x, int y){ return 0 <= x && x < 6 && 0 <= y && y < 6; }
  int countMoves(vector <string> board){
    board[4][4] = board[4][5] = board[5][4] = board[5][5] = 'd';
    
    map<vector<string>, int> dp;
    queue<vector<string>> Q;
    Q.push(board);
    dp[board] = 0;

    while(!Q.empty()){
      vector<string> s = Q.front(); Q.pop();
      if(goal(s)) return dp[s];

      for(int i = 0; i < 6; i++){
	for(int j = 0; j < 6; j++){
	  if(s[i][j] != 'd') continue;

	  for(int k = 0; k < 4; k++){
	    int ny = i + dy[k], nx = j + dx[k];
	    int nyy = i + 2 * dy[k], nxx = j + 2 * dx[k];
	    if(!in(ny, nx)) continue;
	    if(s[ny][nx] == '.'){ //隣接セルに移動
	      vector<string> tmp = s;
	      tmp[i][j] = '.';
	      tmp[ny][nx] = 'd';
	      if(dp.count(tmp) == 0){ 
		dp[tmp] = dp[s] + 1;
		Q.push(tmp);
	      }
	      continue;
	    }

	    if(!in(nyy, nxx)) continue;
	    if((s[ny][nx] == 's' || s[ny][nx] == 'd') && s[nyy][nxx] == '.'){ //隣接セルを飛び越して移動
	      vector<string> tmp = s;
	      tmp[i][j] = '.';
	      tmp[nyy][nxx] = 'd';
	      if(dp.count(tmp) == 0){
		dp[tmp] = dp[s] + 1;
		Q.push(tmp);
	      }
	      continue;
	    }
	  }
	}
      }
    }
    return -1;
  }
};