AOJ2320 Infinity Maze

問題ページ
Infinity Maze | Aizu Online Judge

考えたこと

• Lがめっちゃでかい
• 周期性がありそう
• x,y,向き について考えると40000通りしかないので鳩ノ巣原理から周期は高々40000
• 一回ループに入るまでシミュレーションをしてあとは周期性から求める
• mp[{x,y,向き}] = cnt回目に初めて訪れた としてもっておいて既に訪れたマスに入るまでシミュレート
• マス(x,y)で壁にぶつからない向きまで回転したあとの向きを記録することにした
• 周期loop、r回目からループに入ることがわかった
• l < r なら l回目について答えればいい
• それ以外なら r + (l-r)%loop 回目 について答えればいい
• 向きは1つ前のマスの向きを答えればよい
• 投げたら通った

1-indexedで1ずらしたりするかと思ったら一発で通せてよかった

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }

int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};

string s[105];
VI rec[40010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int h, w, l;
    cin >> h >> w >> l;
    if(!h && !w && !l) return 0;
    REP(i, h) cin >> s[i];

    // スタート地点
    int x=-1, y=-1, dir=-1;
    REP(i, h) REP(j, w) {
      if(s[i][j]=='N') {
        y=i, x=j, dir=0;
      } else if(s[i][j]=='E') {
        y=i, x=j, dir=1;
      } else if(s[i][j]=='S') {
        y=i, x=j, dir=2;
      } else if(s[i][j]=='W') {
        y=i, x=j, dir=3;
      }
    }
    assert(x!=-1&&y!=-1&&dir!=-1);

    // シミュレーション
    int cnt = 0, r = 0, loop = 0;
    map<VI, int> mp;
    while(true) {
      while(true) {
        int nx = x+dx[dir], ny = y+dy[dir];
        if(IN(0LL, w, nx) && IN(0LL, h, ny) && s[ny][nx]!='#') break;
        dir=(dir+1)%4;
      }
      if(mp.find({x,y,dir}) != mp.end()) {
        r = mp[{x,y,dir}];
        loop = cnt - r;
        break;
      }
      mp[{x,y,dir}] = cnt;
      rec[cnt++] = {x,y,dir};
      x += dx[dir], y += dy[dir];
    }

    // 答えを求める
    char c[] = {'N', 'E', 'S', 'W'};
    if(l-r+1 <= 0) {
      // rec[l] が答え
      cout << rec[l][1]+1 << " " << rec[l][0]+1 << " " << c[rec[l-1][2]] << endl;
    } else {
      int tmp = (l-r)%loop;
      // rec[r+tmp] が答え
      cout << rec[r+tmp][1]+1 << " " << rec[r+tmp][0]+1 << " " << c[rec[r+(tmp-1+loop)%loop][2]] << endl;
    }
  }

  return 0;
}