题目链接
#include<bits/stdc++.h> using namespace std; char ma[105][105]; int vis[105][105]; int flag; int dir[4][2] = {1,0,-1,0,0,-1,0,1}; int num; int xx,x2; int yy,y2,m,n; struct node{ int x; int y; int turn; }s,t; int bfs(){ queue<node> q;//在里面初始化队列 node q1; q1.x = s.x; q1.y = s.y; q1.turn = -1; q.push(q1); vis[q1.x][q1.y] = 1; node p; while(!q.empty()){ p = q.front(); q.pop(); if(p.x == t.x && p.y == t.y && p.turn <= num){ flag = 1; return 0; } q1.turn = p.turn + 1;//一个方向都走过了只能转弯了 for(int i = 0; i < 4; i++){ q1.x = p.x+dir[i][0]; q1.y = p.y+dir[i][1]; while(q1.x>=0&&q1.x<m&&q1.y>=0&&q1.y<n&&ma[q1.x][q1.y]!='*'){//一条线上只要能走就走不能把!vis[q1.x][q1.y]放到while里面 if(!vis[q1.x][q1.y]){ vis[q1.x][q1.y]=1; q.push(q1); } q1.x += dir[i][0]; q1.y += dir[i][1]; // cout << q1.x << q1.y << q1.turn << endl; } } } flag = 0; return 0; } int main(){ int T; scanf("%d",&T); for(int i = 0; i < T; i++){ memset(vis,0,sizeof(vis)); flag = 0; scanf("%d%d",&m,&n); for(int j = 0; j < m; j++){ scanf("%s",ma[j]); } scanf("%d%d%d%d%d",&num,&s.y,&s.x,&t.y,&t.x);//因为题目中x代表列所以要反过来 s.x--;s.y--;t.x--;t.y--; if(ma[s.x][s.y]=='*' || ma[t.x][t.y] == '*') flag = 0; else bfs(); if(flag == 0) printf("no\n"); else printf("yes\n"); } return 0; }第二种题解 这种方式也容易理解，关键是有两个坑，第一个要用三维标记数组，第二个为什么在主函数里面就要给定起点方向然后进行四个方向的bfs，这是为了避免可能出现特殊的情况而出现问题，具体样例在代码最后。
#include<bits/stdc++.h> using namespace std; char mp[105][105]; bool vis[105][105][4]; int n,m,k,dir[][2]={-1,0,0,-1,1,0,0,1}; // struct node{ // int x,y,d,t; ///定义状态 d为该结点的方向 处于(x,y)时转了t次 // bool operator <(const node & rs) const{ /// 转完次数越多优先级越小 // return t > rs.t; // } // }s,t; bool check(int x,int y){ if(x<0||x>=n||y<0||y>=m||mp[x][y]=='*')return false; return true; } // int dir[4][2] = {1,0,-1,0,0,-1,0,1}; // int n,m,k; struct node{ int x,y,d,t; bool operator <(const node & a) const{ return t > a.t; } }s,t; // bool check(int x,int y){ // if(x<0||x>=n||y<0||y>=m||mp[x][y]=='*')return false; // return true; // } bool bfs(int d){ priority_queue<node> q; memset(vis,0,sizeof(vis)); s.t = 0; s.d = d; q.push(s); vis[s.x][s.y][d] = 1; while(!q.empty()){ node p = q.top(); q.pop(); //printf("%d %d %d\n",p.x,p.y,p.t); if(p.t > k) return false; if(p.x == t.x && p.y == t.y){ return true; } for(int i = 0; i < 4; i++){ int xx = p.x+dir[i][0]; int yy = p.y+dir[i][1]; if(!check(xx,yy)||vis[xx][yy][i]) continue; vis[xx][yy][i]=1; if(i == p.d) q.push({xx,yy,i,p.t}); else q.push({xx,yy,i,p.t+1}); //printf("%d asd%d %d %d %d\n",i,q.top().x,q.top().y,q.top().t,q.size()); // cout << xx << yy << xturn << endl; } } return false; } int main(){ int tcase; scanf("%d",&tcase); while(tcase--){ // memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(int i = 0; i < n; i++){ scanf("%s",mp[i]); } scanf("%d%d%d%d%d",&k,&s.y,&s.x,&t.y,&t.x); s.x--;s.y--;t.x--;t.y--; if(mp[s.x][s.y]=='*' || mp[t.x][t.y] == '*') {printf("no\n");continue;} bool flag = false; for(int i = 0; i < 4; i++){ flag = bfs(i); if(flag) break; } if(flag) printf("yes\n"); else printf("no\n"); } return 0; } /* 2 5 4 **.* ...* .*.* .*.* ...* 1 1 5 3 1 */