SRM 467 Div2 Hard MazeOnFire

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10695&rd=14151
迷路が与えられる。'#'は壁で、'F'は火、'.'は何もないセル、'$'がプレイヤーのスタート地点である。プレイヤーはスタート地点から出発して毎ターン上下左右の隣接セルで壁か火のないセルに移動できる。火は毎ターン上下左右の壁以外のセルに一セル分広がっていく。プレイヤーが最大限火から逃げられるターン数を求めよ。ずっと逃げ続けられるなら-1を返せ。

やりかた

まずスタート地点から'.'のセルにプレイヤーが移動するまでのターン数を幅優先探索にて求める。続いて火が広がっていくシミュレーションを行う。ある'.'セルが火の手に飲み込まれるターン数(aとする)とスタート地点からそのセルにプレイヤーが移動するターン数(bとする)を比べる。プレイヤーのターン数の方が小さいようならそのセルが火の手に飲み込まれる前にプレイヤーはそのセルに移動できる事になる。そのときの、そのセルが火の手に飲み込まれるターン数(a)を記録しておく。この記録値の最大が答え。
ただし、壁に囲われてずっと逃げ切れるケースがある。これはシミュレーションで火の手がこれ以上広がらなくなった時に、まだ'.'セルが存在し、かつプレイヤーがそのセルに移動できる状況であれば、プレイヤーもずっと逃げ切れるとわかる。

以下ソース。

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int dist[60][60];
bool visited[60][60];

class MazeOnFire {
public:
  int N, M;
  bool valid(int y, int x){
    return 0 <= y && y < N && 0 <= x && x < M;
  }
  int maximumTurns(vector <string> maze) {
    int result = 0;
    N = maze.size();
    M = maze[0].length();
    int sx, sy;
    for(int i = 0; i < N; i++){
      for(int j = 0; j < M; j++){
	if(maze[i][j] == '$')
	  sx = j, sy = i;
	dist[i][j] = INF;
      }
    }
    maze[sy][sx] = '.';
    memset(visited, false, sizeof(visited));
    //memset(dist, -1, sizeof(dist));

    queue<pair<int, int> > Q;
    Q.push(make_pair(sy, sx));
    dist[sy][sx] = 0;
    while(!Q.empty()){
      pair<int, int> q = Q.front(); Q.pop();
      for(int i = 0; i < 4; i++){
	int ny = q.first + dy[i];
	int nx = q.second + dx[i];
	if(valid(ny, nx) && maze[ny][nx] == '.' && !visited[ny][nx]){
	  dist[ny][nx] = min(dist[ny][nx], dist[q.first][q.second] + 1);
	  visited[ny][nx] = true;
	  Q.push(make_pair(ny, nx));
	}
      }
    }

    int cnt = 0;
    bool update = true;
    while(update){
      update = false;
      vector<string> tmp = maze;
      for(int y = 0; y < N; y++){
	for(int x = 0; x < M; x++){
	  if(maze[y][x] == '.'){
	    for(int k = 0; k < 4; k++){
	      if(valid(y + dy[k], x + dx[k]) && maze[y + dy[k]][x + dx[k]] == 'F'){
		tmp[y][x] = 'F';
		update = true;
	      }
	    }
	    if(dist[y][x] <= cnt)
	      result = max(result, cnt + 1);
	  }
	}
      }
      cnt++;
      maze = tmp;
    }
    for(int y = 0; y < N; y++){
      for(int x = 0; x < M; x++){
	if(maze[y][x] == '.' && dist[y][x] != INF) return -1;
      }
    }
    return result;
  }
};

これは正解できた。よかった。