読者です 読者をやめる 読者になる 読者になる

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;
}