BFS【模板题】

广度优先搜索算法（Breadth-First-Search），又译作宽度优先搜索，或横向优先搜索，简称BFS，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct node
{
int x,y,step;
};
char map[105][105];
int vis[105][105];
int to[4][2]={0,1,0,-1,1,0,-1,0};
int n,m,sx,sy,ans;
int check(int x,int y)
{
if(x<0||x>=n||y<0||y>=m)return 1;
if(vis[x][y]||map[x][y]=='#')return 1;
return 0;
}
void bfs()
{
int i;
queue<node>Q;
node a,next;
a.x=sx;
a.y=sy;
a.step=0;
vis[a.x][a.y]=1;
Q.push(a);
while(Q.empty())
{
Q.front();
Q.pop();
if(map[a.x][a.y]=='E')
{
ans=a.step;
return ;
}
for(i=0;i<4;i++)
{
next=a;
next.x+=to[i][0];
next.y+=to[i][1];
if(check(next.x,next.y))continue;
next.step=a.step+1;
Q.push(next);
}
}
ans=-1;
}
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%s",map[i]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(map[i][j]=='S')
{
sx=i;
sy=j;
}
memset(vis,0,sizeof(vis));
bfs();
printf("%dn",ans);
}
return 0;
}

最后

以上就是感性唇彩为你收集整理的BFS【模板题】的全部内容，希望文章能够帮你解决BFS【模板题】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。