AOJ2320 Infinity Maze
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2320
以下の様なH*Wのグリッドが与えられる
####.
.....
.#S#.
...#.
#.##.
"NEWS"の何れかのアルファベットがおいてある場所を初期位置とする。
真っすぐ進み、壁にぶち当たったら90度回転する。移動した回数がLに達したときの位置と方向を求めよ。
移動できない場合はないし、空のマスは1つ以上存在することが保証されている。
H, W <= 100, L <= 10^18
解法
高々100*100のグリッドなので、(y, x, 向き)が重複するまで移動してみて、それを周期に残りの移動回数の剰余を見れば良いことが分かる。
毎回の移動で移動回数に対しての座標と向きを保持しておき、最終的な位置に該当するメモを読むなどすれば良い。
int main() { int dy[] = {0,-1,0,1}; int dx[] = {-1,0,1,0}; string WNES = "WNES"; int H, W; ll L; for(; cin >> H >> W >> L && (H|W|L);) { string G[100]; rep(i, H) cin >> G[i]; int y = 0, x = 0, k = 0, c = 0; rep(i, H) rep(j, W) if(isalpha(G[i][j])) y = i, x = j, k = WNES.find(G[i][j]); int T[100][100][4]; minus(T); vector<int> ys, xs, ds; while(1) { int ny = y + dy[k], nx = x + dx[k]; while(!in_range(ny, nx, H, W) || G[ny][nx] == '#') (k += 1) %= 4, ny = y + dy[k], nx = x + dx[k]; y = ny, x = nx; c++; if(~T[y][x][k]) { int len = c - T[y][x][k]; (L -= T[y][x][k]) %= len; L += T[y][x][k] - 1; cout << ys[L] + 1 << " " << xs[L] + 1 << " " << WNES[ds[L]] << endl; break; } if(c == L) { cout << y + 1 << " " << x + 1 << " " << WNES[k] << endl; break; } ys.push_back(y), xs.push_back(x), ds.push_back(k); T[y][x][k] = c; } } return 0; }