提示：每个点可以多次搜索，但是要判断是否是较优解，用visit数组保存每个点的最优解，即最少转弯次数。
#include<iostream> #include<cstdio> #include<queue> #include<memory.h> using namespace std; struct node{ int x,y,direction; int turn; }; int tnum,si,sr,ei,er,h,l; char map[101][101]; int visit[101][101]; #define reset(f,n) memset(f,0,sizeof(f)); int dire[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; void bfs() { int i,r,t; queue<node> qlist; node head; head.x=si-1; head.y=sr-1; head.direction=-1; head.turn=0; visit[si-1][sr-1]=0; qlist.push(head); while(!qlist.empty()) { node nownode=qlist.front(); qlist.pop(); int k=4; while(k--) { i=nownode.x+dire[k][0]; r=nownode.y+dire[k][1]; // cout<<i<<" "<<r<<endl; if(map[i][r]=='.'&&i<h&&i>=0&&r<l&&r>=0) { if(nownode.direction!=-1&&nownode.direction!=k) { t=nownode.turn+1; } else t=nownode.turn; if(t>tnum)continue; if(i==ei-1&&r==er-1) { //cout<<temp.x<<" "<<temp.y<<" "<<temp.turn<<" "<<temp.direction<<" "; cout<<"yes"<<endl; return; } if(visit[i][r]>=t){ node temp; temp.x=i; temp.y=r; temp.direction=k; temp.turn=t; qlist.push(temp); visit[i][r]=t; //cout<<i<<" "<<r<<endl; } } } } cout<<"no"<<endl; return; } int main() { int n; int i,r; cin>>n; while(n--) { reset(visit,0); cin>>i>>r; h=i; l=r; for(int i1=0;i1<i;i1++) for(int r1=0;r1<r;r1++) { cin>>map[i1][r1]; visit[i1][r1]=50; } cin>>tnum>>sr>>si>>er>>ei; bfs(); } return 0; }