AOJ 2320:Infinity Maze

問題リンク：Infinity Maze | Aizu Online Judge

問題概要：
H＊W(1 <= H,W <= 100)の迷路と可能なステップ数L(1 <= L <= 10^18)が与えられる
迷路の中には１つロボットが置いてある
そのロボットをL回動かした後に居るセルとロボットが向いている方向を答えろ

ロボットが壁、または迷路の外にでようとしたときは右に９０度回転する
これはステップにカウントしない

解法：
visited[y][x][dir] := セル(x,y)に方向dirを向いて最初にきたときのステップ数
という配列を用意してシュミレーションする
配列は最初-1で初期化しておき、今後訪れたセルの値が-1でないのであればそこはループになっているのでループにかかる回数でmodをとり残りを再度シュミレーションする
Lが最大10^18なのでintでとるとTLEになるので注意

コード：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#define F first
#define MAX 1000
#define S second
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
typedef pair<int,int> P;
struct Pox
{
  int x,y,dir;
  Pox(int x=-1,int y=-1,int dir=-1):x(x),y(y),dir(dir){}
};
int dx[] = {+0,+1,+0,-1};//N,E,S,W
int dy[] = {-1,+0,+1,+0};
char G[MAX][MAX];
int visited[MAX][MAX][4];
P src;

int getDir(char c)
{
  switch(c)
    {
    case 'N':
      return 0;
    case 'E':
      return 1;
    case 'S':
      return 2;
    case 'W':
      return 3;
    }
}

char toChar(int c)
{
  switch(c)
    {
    case 0:
      return 'N';
    case 1:
      return 'E';
    case 2:
      return 'S';
    case 3:
      return 'W';
    }
}

int main()
{
  int H,W;
  long long L;
  while(cin >> H >> W >> L,H|W|L)
    {
      int dir;
      rep(i,H)
	{
	  string line;
	  cin >> line;
	  rep(j,line.size())
	    {
	      assert(j < W);
	      G[i][j] = line[j];
	      if(!(G[i][j] == '.' || G[i][j] == '#'))src = P(j,i),dir = getDir(G[i][j]),G[i][j] = '.';
	      
	      rep(k,4)visited[i][j][k] = -1;
	    }
	}     

      long long phase = 0;
      vector<Pox> path;
      path.push_back(Pox(src.F,src.S,dir));

      while(true)
	{
	  if(phase >= L)
	    {
	      cout << src.S+1 << " " << src.F+1 << " " << toChar(dir) << endl;  
	      break;
	    }
	  if(visited[src.S][src.F][dir] != -1)
	    { 
	      L -= phase;
	      L %= (phase-visited[src.S][src.F][dir]);
	      L += (phase-visited[src.S][src.F][dir]);
	      for(int i=0;i<L;i++)
		{
		  src.F += dx[dir];
		  src.S += dy[dir];
		  
		  if(!(0 <= src.F && src.F < W && 0 <= src.S && src.S < H))
		    {
		      src.F -= dx[dir];
		      src.S -= dy[dir];
		      dir = (dir+1)%4;
		      i--;
		      continue;
		    }
		  else if(G[src.S][src.F] == '#')
		    {
		      src.F -= dx[dir];
		      src.S -= dy[dir];
		      dir = (dir+1)%4;
		      i--;
		      continue;
		    }	
		}
	   
	      cout << src.S+1 << " " << src.F+1 << " " << toChar(dir) << endl;
	      
	      break;
	    }     
 
	  visited[src.S][src.F][dir] = phase;
	  src.F += dx[dir];
	  src.S += dy[dir];
	  if(!(0 <= src.F && src.F < W && 0 <= src.S && src.S < H))
	    {
	      src.F -= dx[dir];
	      src.S -= dy[dir];
	      dir = (dir+1)%4;
	      continue;
	    }
	  else if(G[src.S][src.F] == '#')
	    {
	      src.F -= dx[dir];
	      src.S -= dy[dir];
	      dir = (dir+1)%4;
	      continue;
	    }
 
	  path.push_back(Pox(src.F,src.S,dir));
	  phase++;
	}
      

    }
  return 0;
}