928 - Eternal Truths

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#define M 301
using namespace std;

int R,C,color[M][M][4],d[M][M][4];
char Maze[M][M];

int BFS(int,int);
int next1[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int next2[4][2]={{-2,0},{2,0},{0,-2},{0,2}};
int next3[4][2]={{-3,0},{3,0},{0,-3},{0,3}};
void FindID(char ch,int&,int&);

int main()
{
    int t,i,n,sx,sy;
    //freopen("in.txt","r",stdin);

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d\n",&R,&C);
        for(i=0;i<R;i++)
            gets(Maze[i]);

        FindID('S',sx,sy);
        n=BFS(sx,sy);

        if(n>=0)
            printf("%d\n",n);
        else
            printf("NO\n");
    }
    return 0;
}

void FindID(char ch,int &x,int &y)
{
    int i,j;
    for(i=0;i<R;i++)
        for(j=0;j<C;j++)
            if(Maze[i][j]==ch)
            {
                x=i;y=j;
                return;
            }
}

int BFS(int sx,int sy)
{
    int i,f,x,y,tx,ty,fx;
    memset(color,0,sizeof(color));
    queue<int>Q,F;

    d[sx][sy][1]=0;
    color[sx][sy][1]=1;
    Q.push(sx);
    Q.push(sy);
    F.push(0);

    while(!Q.empty())
    {
        x=Q.front();Q.pop();
        y=Q.front();Q.pop();

        fx=F.front();
        f=fx%3+1;
        F.pop();

        for(i=0;i<4;i++)
        {
            switch(f)
            {
            case 1:
                tx=x+next1[i][0];
                ty=y+next1[i][1];

                if(tx>=0&&tx<R&&ty>=0&&ty<C &&Maze[tx][ty]!='#'&&color[tx][ty][1]==0)
                {
                    d[tx][ty][1]=fx+1;
                    if(Maze[tx][ty]=='E')return d[tx][ty][1];
                    color[tx][ty][1]=1;
                    Q.push(tx);
                    Q.push(ty);
                    F.push(d[tx][ty][1]);
                }
                break;
            case 2:
                tx=x+next2[i][0];
                ty=y+next2[i][1];

                if(tx>=0&&tx<R&&ty>=0&&ty<C &&Maze[tx][ty]!='#'&&color[tx][ty][2]==0)
                {
                    if(Maze[x+next1[i][0]][y+next1[i][1]]!='#')
                    {
                        d[tx][ty][2]=fx+1;
                        if(Maze[tx][ty]=='E')return d[tx][ty][2];
                        color[tx][ty][2]=1;
                        Q.push(tx);
                        Q.push(ty);
                        F.push(d[tx][ty][2]);
                    }
                }
                break;
            case 3:
                tx=x+next3[i][0];
                ty=y+next3[i][1];

                if(tx>=0&&tx<R&&ty>=0&&ty<C &&Maze[tx][ty]!='#'&&color[tx][ty][3]==0)
                {
                    if(Maze[x+next1[i][0]][y+next1[i][1]]!='#' && Maze[x+next2[i][0]][y+next2[i][1]]!='#')
                    {
                        d[tx][ty][3]=fx+1;
                        if(Maze[tx][ty]=='E')return d[tx][ty][3];
                        color[tx][ty][3]=1;
                        Q.push(tx);
                        Q.push(ty);
                        F.push(d[tx][ty][3]);
                    }
                }
                break;
            }

        }
    }
    return -1;
}