到同一个点的同一个方向必须转向次数越来越小
#include <bits/stdc++.h>
using namespace std;
char mp[105][105];
int vis[105][105][4];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; //上右下左
struct node{int yy; //图的行坐标 int xx; //图的列坐标 int toward;int cnt;
};
bool dfs(int k,int yy1,int xx1,int yy2,int xx2){stack<node> sta;int cnt=0;mp[yy1][xx1]='*';for(int i=0;i<=3;i++){int yy=yy1+dir[i][0];int xx=xx1+dir[i][1];if(mp[yy][xx]!=0&&mp[yy][xx]!='*'){if(cnt+1<vis[yy][xx][i]){vis[yy][xx][i]=cnt+1;sta.push({yy,xx,i,cnt+1});}}}while(!sta.empty()){auto now=sta.top();sta.pop();//cout<<now.yy<<" "<<now.xx<<" "<<now.toward<<" "<<now.cnt<<" "<<mp[now.yy][now.xx]<<endl;if(now.yy==yy2&&now.xx==xx2){return true;}for(int i=0;i<=3;i++){int yy=now.yy+dir[i][0];int xx=now.xx+dir[i][1];if(mp[yy][xx]!=0&&mp[yy][xx]!='*'){if(i!=now.toward){if(now.cnt<k){if(now.cnt+1<vis[yy][xx][i]){//cout<<yy<<" "<<xx<<" "<<i<<" "<<now.cnt+1<<endl;vis[yy][xx][i]=now.cnt+1;sta.push({yy,xx,i,now.cnt+1});}}}else {if(now.cnt<vis[yy][xx][i]){vis[yy][xx][i]=now.cnt;sta.push({yy,xx,i,now.cnt});}}}}}return false;
}
int main(){int t; scanf("%d",&t);while(t--){int m,n; //m行，n列 scanf("%d%d",&m,&n);memset(mp,0,sizeof(mp));memset(vis,0x3f,sizeof(vis));for(int i=1;i<=m;i++){scanf("%s",mp[i]+1);}int k, xx1,yy1,xx2,yy2;scanf("%d%d%d%d%d",&k,&xx1,&yy1,&xx2,&yy2);if(mp[yy1][xx1]=='*'||mp[yy2][xx2]=='*'){printf("no\n");}else{if(dfs(k+1,yy1,xx1,yy2,xx2)){printf("yes\n");}else printf("no\n");}} return 0;
}