宽度优先搜索模板+题目

宽度优先搜索

也是搜索手段是之一，它余深度优先搜索类似，从一个起点出发探索所有可能的结果，是用队列实现。

#define inf=0x3f3f3f3f;
const int maxn=1000;
//对节点的定义可以用struct 或者有一个stl pair的用法
struct node{
int x;
int y;
}p,pp;
//typedef pair<int ,int> p;
char maze[maxn][maxn];//保存迷宫，如果是那种棋盘的可以不用这个,要自己输入
int m,n;
//实际的要搜索的矩阵大小
int sx,sy;//记录开始搜索位置
int ex,ey;//记录结束位置
int d[maxn][maxn];//记录步数
int dx{1,-1,0,0};
int dy{0,0,1,-1};//移动方式，存入数组可以用for循环遍历
int bfs()
{
queue<struct node>que;//声明要用的队列
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
d[i][j]=inf;
}
}//先给每个点附上初值
p.x=sx;
p.y=sy;
que.push(p);//把初始的起点压入队列开始遍历
d[sx][sy]=0;//令其实那个距离为0
while(que.size())
{
p=que.front();
que.pop();//取出队列最前面那个
if(p.x==ex&&p.y==ey)
break;//遍历到了终点
for(int i=0;i<4;i++)
{
int nx=p.x+dx[i];
int ny=p.y+dy[i];
if(nx>=0&&nx<n&&ny>=0&&ny<m&&d[nx][ny]==inf)
{
pp.x=nx;
pp.y=ny;
que.push(pp);
d[nx][ny]=d[p.x][p.y]+1;
}
}
}
return d[ex][ey];
}
int main()
{
int ans=bfs();
......
}

POJ 1915 Knight Moves
给测试组数，每组数，第一个是这个棋盘的大小，然后就是起点与终点的坐标，找出，从起点到终点的最小距离
题解
基本上套用上面那个模板就过了，还没有模板复杂，不用输入迷宫，然后骑士的走位有点不一样，换好走位基本上就可以过了

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
//typedef pair<int,int> p;
struct node{
int x;
int y;
}p,pp;
int dx[8]={-1,-2,1,2,-2,-1,2,1};
int dy[8]={-2,-1,-2,-1,1,2,1,2};
int d[301][301];
int maze[301][301];
int sx,sy;
int ex,ey;
int n;
int bfs()
{
queue<struct node> que;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
d[i][j]=inf;
}
}
p.x=sx;
p.y=sy;
que.push(p);
d[sx][sy]=0;
while(que.size())
{
p=que.front();
que.pop();
if(p.x==ex&&p.y==ey)
break;
for(int i=0;i<8;i++)
{
int nx=p.x+dx[i];
int ny=p.y+dy[i];
if(nx>=0&&nx<n&&ny>=0&&ny<n&&d[nx][ny]==inf)
{
pp.x=nx;
pp.y=ny;
que.push(pp);
d[nx][ny]=d[p.x][p.y]+1;
}
}
}
return d[ex][ey];
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
cin>>sx>>sy;
cin>>ex>>ey;
int ans=bfs();
printf("%dn",ans);
}
return 0;
}

最后

以上就是懵懂石头为你收集整理的宽度优先搜索模板+题目的全部内容，希望文章能够帮你解决宽度优先搜索模板+题目所遇到的程序开发问题。

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