本文主要是介绍acm算法之bfs,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
/*bfs,此处给出的是poj-3984迷宫问题的模板,输入
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
找到从左上到右下最短的路径,其中值为1的点表示为障碍,不能通过*/
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int s[6][6],visit[6][6];
int dir[4][2]={-1,0,0,-1,0,1,1,0};
struct node
{
int x;
int y;
int step;
int a[50];
};
node bfs(int x,int y)
{
memset(visit,0,sizeof(visit));
queue<node>q;
node m,n;
m.x=x;
m.y=y;
visit[x][y]=1;
m.step=0;
q.push(m);
while(!q.empty())
{
m=q.front();
q.pop();
if(m.x==4&&m.y==4)
{
return m;
}
for(int i=0;i<4;i++)
{
n=m;//注意此处易错,m含有的a[n]数组含有之前每一步的信息,所以必须要有这一步,得到前面各点的方向信息
n.x=m.x+dir[i][0];
n.y=m.y+dir[i][1];
if(n.x>=0&&n.y>=0&&n.x<5&&n.y<5&&visit[n.x][n.y]==0&&s[n.x][n.y]==0)
{
n.step=m.step+1;
visit[n.x][n.y]=1;
n.a[m.step]=i;//巧妙的办法,通过记录从开头到最后每一步的转向,就可以得到想要的路径
q.push(n);
}
}
}
return m;
}
void print(node w)
{
int fx=0,fy=0;
for(int i=0;i<=w.step;i++)
{
printf("(%d, %d)\n",fx,fy);
if(i!=w.step)//注意,此处虽然把这个if判断删去,答案依旧是对的,但是,W.Step这部没有a[i]的值,没有这个if语句就会越界
{
fx=fx+dir[w.a[i]][0];
fy=fy+dir[w.a[i]][1];
}}
}
int main(void)
{
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
scanf("%d",&s[i][j]);
}
}
node w=bfs(0,0);
print(w);
}
这篇关于acm算法之bfs的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!