学步园

#include <cstdio>
#include <queue>
using namespace std;
const int M=110;
int visit[M][M];
char map[M][M];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int t,m,n,x1,y1,x2,y2,k,i,r,tx,ty;
char ch;
struct node
{
    int x,y,turn,dir;
};

bool check(int x,int y)
{
    if(x>=1 && x<=m && y>=1 && y<=n)
        return true;
    return false;
}

bool bfs()
{
    queue<node> v;
    node p,temp;
    p.x=x1, p.y=y1, p.turn=-1, p.dir=-1;
    v.push(p); visit[x1][y1]=1; 
    while( !v.empty() )
    {
        p=v.front(); v.pop();
        if( p.x==x2 && p.y==y2 && p.turn<=k )
            return 1;
        if( p.turn>k )
            continue;
        for(i=0;i<4;i++)
        {

            tx=p.x+dir[i][0];
            ty=p.y+dir[i][1];
            if( map[tx][ty-1]=='*' || !check(tx,ty) )
                continue;
            temp.x=tx; temp.y=ty; temp.turn=p.turn; temp.dir=i;
            if( i!=p.dir ) temp.turn++;
            if( check(tx,ty) && temp.turn<=visit[tx][ty] )
            {
                v.push(temp);
                visit[tx][ty]=temp.turn;
            }
        }
    }
    return 0;
}

int main()
{
    // freopen("cin","r",stdin);
    // freopen("cout","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        for(i=1;i<=m;i++)
            for(r=1;r<=n;r++) visit[i][r]=99999999;
        for(i=1;i<=m;i++)
            scanf("%s",map[i]);
        scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);      
        if( bfs() )
            printf("yes\n");
        else
            printf("no\n");
    }
}