01bfs

正常的bfs 边权为1，而题目中有转向次数的限制，所以可以把转向看作是边权为1，向着原方向前进看作是边权为0,使用01bfs 把边权为0的点放入队头为1的放入队尾，这样保证的bfs队列的单调性，和二段性可以想到先出队的一定是当前全局到达这个点转向最少的，后面如果出现了这个点的话，必定不是最短的，因此在出队是令st为1 .=

在普通的bfs里从这一点出发到达相邻点的边权都是1，所d以到达这个点就是最短的路，而在这个bfs里到达相邻点的边可能不一样，因此到达别的点也不一样所以需要多开一维度表示方向，记录这个方向上第一次到达的最小值。

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
int t;
int m,n;
const int N=110;
bool st[N][N][4];
int x,y,x2,y2;
int k;
char s[N][N];
struct node
{
  int x,y;
  int z;
};
int dist[N][N][4];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
bool bfs()
{
    memset(st,0,sizeof st);
    memset(dist,0x3f,sizeof dist);
    deque<node>q;
    for(int i=0;i<4;i++)
    {
        q.push_back({x,y,i});
        dist[x][y][i]=0;
    }
    while(q.size())
    {
       auto [x,y,z]=q.front();
       q.pop_front();
       if(st[x][y][z])continue;
       st[x][y][z]=1;
       if(dist[x][y][z]>k)return false;//因为bfs队列是递增的,如果队头的转弯次数大于k了，代表以后都大于k;
       if(x==x2&&y==y2){

           return true;
       }
       for(int i=0;i<4;i++)
       {
           int x1=x+dx[i];
           int y1=y+dy[i];
           int w= z!=i;
           if(x1<1||x1>n||y1<1||y1>m)continue;

           if(st[x1][y1][i])continue;
           if(s[x1][y1]=='*')continue;
           if(dist[x1][y1][i]>dist[x][y][z]+w) 
           {

               dist[x1][y1][i]=dist[x][y][z]+w;
               if(w)q.push_back({x1,y1,i});
               else q.push_front({x1,y1,i});
           }
       }
    }
    return false;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>s[i]+1;
        cin>>k>>x>>y>>x2>>y2;
        swap(x,y);
        swap(x2,y2);
        if(bfs())cout<<"yes\n";
        else cout<<"no\n";
    }
}