题解：记录转弯次数，直接广搜即可
#include<cstdio> #include<queue> using namespace std; char map[102][102]; int n,m,bx,by,ex,ey,k,mark[102][102]; int dir1[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; struct node { int x,y,step,dir; }; void bfs() { node t; queue<node>q; int i; t.x=bx;t.y=by;t.step=0;t.dir=-1; mark[bx][by]=0; q.push(t); while(!q.empty()) { t=q.front(); q.pop(); for(i=0;i<4;i++) { node tt=t; tt.x+=dir1[i][0]; tt.y+=dir1[i][1]; if(tt.x<0||tt.x>n-1||tt.y<0||tt.y>m-1||map[tt.x][tt.y]=='*') continue; if(tt.dir!=i&&tt.dir!=-1)tt.step++; if(tt.step>k)continue; if(tt.x==ex&&tt.y==ey) { printf("yes "); return ; } if(mark[tt.x][tt.y]>=tt.step) { tt.dir=i; mark[tt.x][tt.y]=tt.step; q.push(tt); } } } printf("no "); return ; } int main() { int i,j,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=0;i<n;i++) for(j=0;j<m;j++) mark[i][j]=999; for(i=0;i<n;i++) scanf("%s",map[i]); scanf("%d%d%d%d%d",&k,&by,&bx,&ey,&ex); --by;--bx;--ey;--ex; if(by==ey&&bx==ex) { printf("yes "); continue; } bfs(); } return 0; }