学步园

广搜

#include "stdio.h"
#include "string.h"
#include<queue>
using namespace std;
struct team
{
    int x,y,crow;
};
char map[101][101];
int a[4][2]={1,0,-1,0,0,1,0,-1},flag[110][110];
int n,m,p,sx,sy,ex,ey;
int judge(int x,int y)
{
    if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]=='.')
        return 1;
    return 0;
}
int bfs()
{
    if(sx==ex&&sy==ey)
        return 1;
    queue<team>q;
     team cur,next;
     int x,y,k,i;
     memset(flag,0,sizeof(flag));
     flag[sx][sy]=1;
     cur.x=sx;cur.y=sy;cur.crow=-1;
        q.push(cur);
     while(!q.empty())
     {
         cur=q.front();
         q.pop();
         for(i=0;i<4;i++)
         {
             x=cur.x+a[i][0];
             y=cur.y+a[i][1];
            while(judge(x,y))
             {    
                if(flag[x][y]==0)
                { 
                    next.x=x;
                   next.y=y;
                 next.crow=cur.crow+1;
                 if(x==ex&&y==ey&&next.crow<=p)
                     return 1;                 
                   q.push(next);
                   flag[x][y]=1;
                }
                   x=x+a[i][0];
                   y=y+a[i][1];
             }

         }
     }
     return 0;
}
     
      
int main()
{
    
    int i,a,b,j;
      scanf("%d",&a);
          while(a--)
    {
        scanf("%d %d",&n,&m);
        getchar();
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
             scanf(" %c",&map[i][j]);
            getchar();
        }
        scanf("%d%d%d%d%d",&p,&sy,&sx,&ey,&ex);
        sx=sx-1;sy=sy-1;ex=ex-1;ey=ey-1;
        if(bfs())
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}