尼玛，就因为没发现‘yes’写成‘yrs’。整整让哥找了一个小时的bug。有没有..........此刻，内流满面！

 

分析：

开始以为是单纯的BFS,结果WA无数次！！

后来分析后发现是要找到不超过转向次数的转向路径,

最重要的是已经访问的节点不能直接标记为已经访问。因为存在远距离但是转向少的情况,所以要标记上每一个已经访问的点到起点所需要的转弯次数。

#include<cstdio>                //这题和连连看一样，走过的点可以再次访问

#include<queue>

#include<cstring>

using namespace std;

#define inf 1000000

int result;                     //初始化为0，结果能走到就为1

char map[105][105];

int visit[105][105];             //初始化为inf ，visit[i][j] 记录走过该点是的最小转弯次数

int fang[4][2]={

{0,-1},{0,1},{1,0},{-1,0}};

int  n,m;

struct node

{

 int x;

 int y;

 int d;        //记录当前该点的方向

 int num;

};

 

void bfs(int k,int x1,int y1,int x2,int y2)

{

 queue<node> qu;

 int i,j;

 node t,tt;

 t.x=x1;

 t.y=y1;

 t.d=-1;

 t.num=0;

 visit[x1][y1]=0;

 qu.push(t);

 

 while(!qu.empty())

 {

  t=qu.front();

  qu.pop();

  if(t.x==x2&&t.y==y2&&t.num<=k)

  {

   result=1;

   return ;

  }

  

  for(i=0;i<4;i++)

  {

   tt.x=t.x+fang[i][0];

   tt.y=t.y+fang[i][1];

   

   if(t.d==-1)

   tt.num=0;

   else if(t.d!=i)

   tt.num=t.num+1;

   else

   tt.num=t.num;

   

   tt.d=i;

   if(tt.x<1||tt.y<1||tt.x>m||tt.y>n)

   continue;

   if(map[tt.x][tt.y]=='.'&&tt.num<=visit[tt.x][tt.y])

   {

    visit[tt.x][tt.y]=tt.num;

    qu.push(tt);

   }

  }

 }

}

int main()

{

 int i,j;

 int t;

 int k,x1,y1,x2,y2;

 scanf("%d",&t);

 while(t--)

 {

  scanf("%d%d",&m,&n);                 //m行，n列

  getchar();

  for(i=1;i<=m;i++)

  {

   for(j=1;j<=n;j++)

   {

    scanf("%c",&map[i][j]);

    visit[i][j]=inf;

   }

   getchar();

  }

  scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);

  

  result=0;

  bfs(k,x1,y1,x2,y2);

  if(result==1)

  printf("yes\n");

  else

  printf("no\n");

 }

 return 0;

}