本文主要是介绍BFS--cf793b Igor and his way to work，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
从起点走到终点，最多只能转2次弯，求是否能到达终点。
如果用dfs，会因为重复状态过多超时。
所以需要bfs，并且记录是否访问过。
由于有方向和转弯次数的限制，所以需要一起在vis中记录。
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 1000 + 5;
char mp[maxn][maxn];
const int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
struct point {
int x,y;
}s,t;
struct node{
int x,y;
int d,turn;//剩余的转弯次数
};
bool succ = false;
int vis[maxn][maxn][4][3];//x y dir turn
int n,m;
void bfs()
{
queue<node> q;
int tx,ty;
for (int i = 0; i < 4; i ++) {
tx = s.x + dir[i][0];
ty = s.y + dir[i][1];
if(tx >= 0 && ty >= 0 && tx < n && ty < m && mp[tx][ty] != '*'){
q.push({tx,ty,i,2});
vis[tx][ty][i][2] = 1;}
}
while (!q.empty()) {
node tmp = q.front();q.pop();
if(tmp.x == t.x && tmp.y == t.y) {succ = true;break;}
for (int i = 0; i < 4; i ++) {
int tx = tmp.x + dir[i][0];
int ty = tmp.y + dir[i][1];
if(tx >= 0 && ty >= 0 && tx < n && ty < m && mp[tx][ty] != '*'){
if(i == tmp.d)
{
if(!vis[tx][ty][i][tmp.turn]){
vis[tx][ty][i][tmp.turn] = 1;
q.push({tx,ty,i,tmp.turn});
}
}
else{
if(tmp.turn > 0)
{
if(!vis[tx][ty][i][tmp.turn - 1]){
vis[tx][ty][i][tmp.turn - 1] = 1;
q.push({tx,ty,i,tmp.turn - 1});
}
}
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
getchar();
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++) {
scanf("%c",&mp[i][j]);
if(mp[i][j] == 'S') {s.x = i,s.y = j;}
else if (mp[i][j] == 'T') {t.x = i,t.y = j;}
}
getchar();
}
bfs();
if(succ) printf("YES\n");
else printf("NO\n");
return 0;
}
这篇关于BFS--cf793b Igor and his way to work的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
