SRM 541 Div2 Hard NonXorLife

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11890&rd=14733
'o'か'.'かで埋められたグリッドが与えられる。'o'のマスは毎ターンごとに隣接する上下左右のマスを'o'に塗り替えていく。Kターン後の'o'のマス数を求めよ。
K <= 1000, グリッドの初期サイズ <= 1000x1000

やりかた

単純な幅優先探索によるシミュレーションでOK。
あるマスが'o'に塗り替えられる最短のターン数を記録しておき、最終的にKターン以内のものがいくつあるか調べる。

以下ソース。

class NonXorLife {
public:
  int countAliveCells(vector <string> field, int K) {
    int result = 0;
    int N = field.size();
    int M = field[0].length();
    for(int i = 0; i < MAX; i++) fill(dist[i], dist[i] + MAX, INF);

    queue<pair<int, int> > Q;
    for(int i = 0; i < N; i++)
      for(int j = 0; j < M; j++)
	if(field[i][j] == 'o'){
	  Q.push(make_pair(i + offset, j + offset));
	  dist[i + offset][j + offset] = 0;
	}
    
    while(!Q.empty()){
      int y = Q.front().first;
      int x = Q.front().second;
      Q.pop();
      for(int i = 0; i < 4; i++){
	int ny = y + dy[i], nx = x + dx[i];
	if(ny < 0 || MAX <= ny || nx < 0 || MAX <= nx) continue;
	if(dist[ny][nx] <= dist[y][x] + 1) continue;
	dist[y + dy[i]][x + dx[i]] = dist[y][x] + 1;
	Q.push(make_pair(y + dy[i], x + dx[i]));
      }
    }
    
    for(int i = 0; i < MAX; i++)
      for(int j = 0; j < MAX; j++)
	if(dist[i][j] <= K) result++;

    return result;
  }
};

あとすこし。あとすこし。