SPOJ: QUEEN — Wandering Queen(2nd Edition)

#include<bits/stdc++.h>
#define sz 1005
using namespace std;
const int dx[]= {1,1,0,-1,-1,-1,0,1};
const int dy[]= {0,1,1,1,0,-1,-1,-1};
struct node
{
    int x,y,dir,mov;
    node()
    {
        x=y=mov=0;
        dir=-1;
    }
};
char str[sz][sz];
int vis[sz][sz][10];
int dis[sz][sz];
int n,m;
queue<node> qq;
int bfs(node S,node F)
{
    int i,j,k,l,row,col,mn,cost;
    bool key;
    mn=INT_MAX;
    vis[S.x][S.y][0]=0;
    vis[S.x][S.y][1]=0;
    vis[S.x][S.y][2]=0;
    vis[S.x][S.y][3]=0;
    vis[S.x][S.y][4]=0;
    vis[S.x][S.y][5]=0;
    vis[S.x][S.y][6]=0;
    vis[S.x][S.y][7]=0;
    dis[S.x][S.y]=0;
    qq.push(S);
    node uu,vv;
    key=false;
    while(!qq.empty())
    {
        uu=qq.front();
        qq.pop();
        for(i=0; i<8; i++)
        {
            row=dx[i]+uu.x;
            col=dy[i]+uu.y;
            if(uu.dir==-1)     cost=1;
            else if(uu.dir!=i)
            {
                cost=uu.mov+1;
            }
            else
            {
                cost = uu.mov;
            }
            if((row>=1 && row<=n) &&(col>=1 && col<=m) && str[row][col]!='X' && cost<=vis[row][col][i])
            {

                if(row==F.x and col==F.y)
                {
                    vis[row][col][i]=min(vis[row][col][i],cost);
                    dis[row][col]=min(dis[row][col],vis[row][col][i]);
                    key=true;
                }
                else
                {
                    vis[row][col][i]=min(vis[row][col][i],cost);
                    dis[row][col]=min(dis[row][col],vis[row][col][i]);
                    vv.x=row;
                    vv.y=col;
                    vv.dir=i;
                    vv.mov=cost;
                    qq.push(vv);
                }
            }
        }
    }
    if(key) return dis[F.x][F.y];
    return -1;
}
int main()
{
    int i,tt,j,k,l,rec,store,now,pore,baki;
    node S,F;
    int tx,ty,sx,sy;
    char ch;
    scanf("%d",&tt);
    getchar();
    while(tt--)
    {
        memset(vis,20,sizeof(vis));
        memset(dis,20,sizeof(dis));
        //printf("vis = %d\n",vis[56][78]);
        scanf("%d %d",&n,&m);
        getchar();
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m; j++)
            {
                ch=getchar();
                if(ch=='S')
                {
                    sx=i,sy=j;
                }
                if(ch=='F')
                {
                    tx=i,ty=j;
                }
                str[i][j]=ch;
            }
            getchar();
        }
        if(n==1 && m==1){
            printf("-1\n");
            continue;
        }
        S.x=sx;
        S.y=sy;
        S.mov=0;
        S.dir=-1;

        F.x=tx;
        F.y=ty;

        printf("%d\n",bfs(S,F));
        while(!qq.empty()) qq.pop();
    }
    return 0;
}


/*
3
3 3
S..
...
..F
3 3
S..
XX.
F..
3 3
S..
XXX
..F


6
2 2
SF
..
2 2
S.
F.
2 2
S.
.F
2 2
SX
XF

1
5 5
SF...
.X.X.
...X.
.X...
X...X


1
3 4
S...
XXX.
XFXX

1
4 4
S...
....
....
...F

1
5 6
...F..
..XX..
.XSX..
...XX.
......
*/