JAG 模擬地区予選 2011 A問題

ICPC

解法

愚直にやるとO(L)で間に合わないのでループを見つける．
計算量は100*100*4なので間に合う．

実装(C++)

intとlong longを間違えていて1WA

#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <iomanip>
#include <functional>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iterator>
#include <sstream>
using namespace std;
#define REP(i,x) for(int i=0;i<(int)x;i++)
#define FOR(it,x) for(__typeof(x.begin()) it=x.begin();it!=x;it++)
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
char d[4]={'E','S','W','N'};
typedef long long lli;
char MAP[101][101];
lli dp[101][101][4];

int main() {
        lli W,H,L;
        while(cin>>H>>W>>L){
                if(H==0)break;
                int sx,sy,sd;
                for(int i=0;i<H;i++){
                        string tmp;
                        cin>>tmp;
                        for(int j=0;j<W;j++){
                                if(tmp[j]!='.'&&tmp[j]!='#'){
                                        for(int k=0;k<4;k++){
                                                if(tmp[j]==d[k]){
                                                        sd=k;sx=j;sy=i;
                                                }
                                        }
                                        tmp[j]='.';
                                }
                                MAP[j][i]=tmp[j];
                        }
                }
                memset(dp,-1,sizeof(dp));
                bool ac=false;
                for(;L--;){
                        if(ac==false&&dp[sx][sy][sd]>=0){
                                L%=(dp[sx][sy][sd]-L);
                                ac=true;
                        }
                        dp[sx][sy][sd]=L;
                        int nx=sx+dx[sd],ny=sy+dy[sd];
                        if(nx>=0&&nx<W&&ny>=0&&ny<H&&MAP[nx][ny]!='#'){
                                sx=nx;sy=ny;
                        }else{
                                L++;
                                sd=(sd+1)%4;
                        }
                }
                cout<<sy+1<<" "<<sx+1<<" "<<d[sd]<<endl;
        }
        return 0;
}