之前用DFS做的，结果超时，看了别人的做法才做出来，现在用BFS做了，明显感觉用BFS容易多了
#include#include #include #include using namespace std; char map[105][105]; int v[105][105];//记录起点到达每个点的最少转弯次数 int d[4][2] = { {1,0},{-1,0},{0,-1},{0,1} }; int begin_x,begin_y,end_x,end_y; int flag,n,m,num; struct node { int x,y; int change_d;//记录改变方向的次数 int d;//记录方向 }; void bfs() { queue q; node s,temp; s.x = begin_x; s.y = begin_y; s.change_d = 0; s.d = -1; v[s.x][s.y] = 0;//起点转弯数 q.push(s); while(!q.empty()) { temp = q.front(); q.pop(); if(temp.x == end_x && temp.y == end_y && temp.change_d <= num) { printf("yes\n"); flag = 1; return ; } for(int i = 0 ; i < 4 ; i ++) { s = temp; s.x += d[i][0]; s.y += d[i][1]; if(s.x < 0 || s.x > = n || s.y < 0 || s.y >= m || map[s.x][s.y] == '*') continue; /*s.d！=-1表示不在起点处，在起点处往哪个方向都可以，转弯次数不增加*/ if(s.d != -1 && i != s.d)//i=0,1,2,3分别表示不同的方向 s.change_d ++; s.d = i; if(s.change_d > num) continue; if(s.change_d <= v[s.x][s.y]) { v[s.x][s.y] = s.change_d; q.push(s); } } } } int main() { //freopen("in.txt","r",stdin); int i,T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i = 0 ; i < n ; i ++) scanf("%s",map[i]); scanf("%d%d%d%d%d",&num,&begin_y,&begin_x,&end_y,&end_x); begin_x--; begin_y--; end_x--; end_y--;//题目给出的行和列都是从1开始计算的，不是从0 memset(v,1,sizeof(v));//先将转弯数初始化最大值 flag = 0; bfs(); if(!flag) printf("no\n"); } return 0; }