kmjp's blog

競技プログラミング参加記です

TopCoder SRM 541 Div2 Hard NonXorLife

Div2 Hardとしては妙に簡単なやるだけゲー。
http://community.topcoder.com/stat?c=problem_statement&pm=11890

問題

無限大の2次元グリッド上で、いくつかのaliveなセルが与えられる。
各セル1ターンごとに以下のように遷移する。

  • 自分のマスまたは上下左右の隣接マスのいずれかがaliveなら、aliveになる
  • そうでなければdeadになる。

Kターン後のaliveマスの数を答えよ。

解法

1つ目の条件より、一度aliveになったマスはdeadにならない。
よって、単純にK回ループを回して新規aliveマスをBFSしていけばよい。

int isis[3200][3200];

class NonXorLife {
	public:
	int countAliveCells(vector <string> field, int K) {
		int i,x,y,d,res=0;
		ZERO(isis);
		set<pair<int,int> > nn;
		FOR(y,field.size()) FOR(x,field[y].size()) if(field[y][x]=='o')
			isis[y+1510][x+1510]=1,nn.insert(make_pair(y+1510,x+1510)),res++;
		
		FOR(i,K) {
			set<pair<int,int> > ne;
			ITR(it,nn) {
				FOR(d,4) {
					int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
					int tx=it->second+dx[d];
					int ty=it->first+dy[d];
					if(isis[ty][tx]==0) {
						res++;
						isis[ty][tx]=1;
						ne.insert(make_pair(ty,tx));
					}
				}
			}
			
			swap(nn,ne);
			ne.clear();
		}
		return res;
		
	}
};

まとめ

この問題は何も考えることがないように見えるが、なぜDiv2とはいえHardに配置された?

広告を非表示にする