928:Eternal Truths

問題文
http://uva.onlinejudge.org/external/9/928.html

進む距離を1,2,3,1,2,3のように繰り返してSからEにいくときの最短ステップ数を出力せよ。行けない時はNOと出力せよ。

幅優先探索した。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
#include<cctype>
#include<queue>
#define INF 100000000
  
using namespace std;
  
int h,w,cost[4][301][301];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
  
struct state{
    state(){}
    state(int x,int y,int moves,int cost):x(x),y(y),moves(moves),cost(cost){}
    int x,y,moves,cost;
};
  
string grid[301];
  
void bfs(state s){
      
    queue<state>que;
    que.push(s);
      
    while(!que.empty()){
        state v=que.front();
        que.pop();
        int mv=v.moves%3+1;
        if(v.cost>=cost[mv][v.y][v.x])continue;
          
        cost[mv][v.y][v.x]=v.cost;
          
        for(int i=0;i<4;i++){
            int nx=v.x+dx[i]*mv,ny=v.y+dy[i]*mv;
            if(nx<0 || ny<0 || w<=nx || h<=ny)continue;
              
            for(int j=1;j<=mv;j++)
                if(grid[v.y+dy[i]*j][v.x+dx[i]*j]=='#')goto end;
              
            que.push(state(nx,ny,v.moves+1,v.cost+1));
              
            end:;
        }
          
    }
}
  
int main(void){
    int n;
    cin >> n;
    while(n--){
        cin >> h >> w;
        for(int i=0;i<h;i++)cin >> grid[i];
          
        for(int i=0;i<4;i++){
            for(int j=0;j<301;j++){
                for(int k=0;k<301;k++){
                    cost[i][j][k]=INF;
                }
            }
        }
          
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(grid[i][j]=='S'){
                    bfs(state(j,i,0,0));
                	goto endloop;
                }
            }
        }
        endloop:;
    	
        int ans=INF;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(grid[i][j]=='E'){
                    for(int k=0;k<4;k++)
                        ans=min(ans,cost[k][i][j]);
                    goto end;
                }
            }
        }
        end:;
        if(ans>=INF)cout << "NO" << endl;
        else cout << ans << endl;
    }
      
    return 0;
}