0210 - The Squares
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0210
シミュレーションするだけの問題。
綺麗にかけた(気がする)のでソースを貼っておく。
人を構造体などで管理せず、場の状況を文字の配列でのみ管理した。
int dx[] = {1,0,-1,0}; int dy[] = {0,-1,0,1}; string str = "ENWS"; int main() { int w,h; while(cin>>w>>h,w||h) { char ba[w][h]; REP(y,h) REP(x,w) cin >> ba[x][y]; int res = -1; REP(time, 180) { int man = 0; REP(y,h) { REP(x,w) { REP(i,4) { if (ba[x][y] == str[i]) { man++; REP(k,4) { int d = (i+3+k)%4; int xx = x+dx[d]; int yy = y+dy[d]; if (ba[xx][yy]=='X'||ba[xx][yy]=='.') { ba[x][y] = str[d]; goto OUT; } } } } OUT:; } } char next[w][h]; memcpy(next, ba, sizeof(ba)); REP(x,w) { REP(y,h) { if (ba[x][y] != '.' && ba[x][y] != 'X') continue; REP(k,4) { int xx = x+dx[k]; int yy = y+dy[k]; if (xx<0||xx>=w||yy<0||yy>=h) continue; if (ba[xx][yy] == str[(k+2)%4]) { if (ba[x][y] == '.') next[x][y] = ba[xx][yy]; else man--; next[xx][yy] = '.'; break; } } } } if (man==0) { res = time + 1; break; } memcpy(ba,next,sizeof(next)); } if (res>=0) cout << res << endl; else cout << "NA" << endl; } }