地图类BFS模版（自用）

这一篇博客主要为了记录地图类题目的BFS步骤
以HDU1242为例子（有一点要注意的就是这题用的是优先队列，平常用普通队列）

[代码]

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
char a[205][205];//0.变量设置，地图数组变量，vis变量，方向变量，起始位置变量
bool vis[205][205];
int dire[4][2] = { { 1,0 },{ 0,1 },{ -1,0 },{ 0,-1 } };
int rx, ry;
int ans;
struct Node//6.设置节点结构体
{
int x, y;
int cnt;
friend bool operator<(Node a, Node b)
{
return a.cnt>b.cnt;
}
}sc, now;
void findR(int n, int m)//4.获得开始位置
{
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
if (a[i][j] == 'r')
{
rx = i;
ry = j;
return;
}
}
}
}
void bfs()
{
priority_queue<Node>q;//7.设置队列（或优先队列）
sc.x = rx;//8.第一个节点的push
sc.y = ry;
sc.cnt = 0;
q.push(sc);
while (q.size())//9.while
{
now = q.top();//10.获得top（）
q.pop();//11.pop（）；
if (a[now.x][now.y] == 'a')//12.BFS终点判断
{
ans = now.cnt;
return;
}
for (int i = 0; i < 4; i++)//13.遍历方向
{
int nowx = now.x + dire[i][0], nowy = now.y + dire[i][1];//14.获得当前xy
if (!vis[nowx][nowy] && a[nowx][nowy] != '#')//15.没访问过&&不是墙（依据题目加条件）
{
vis[nowx][nowy] = 1;//16.vis置1
sc.x = nowx;//17.更新sc结构体所有属性
sc.y = nowy;
if (a[nowx][nowy] == 'x')sc.cnt = now.cnt + 2;
else sc.cnt = now.cnt + 1;
q.push(sc);//18.push（）
}
}
}
}
int main()
{
int n, m;
while (cin >> n >> m)//1.输入
{
memset(a, '#', sizeof(a));//2.初始化设置墙体
memset(vis, 0, sizeof(vis));//3.初始化vis数组
for (int i = 1; i <= n; i++)
{
scanf("%s", a[i] + 1);
}
for (int i = 1; i <= n; i++)
{
a[i][m + 1] = '#';
}
findR(n, m);//4.获得开始位置
ans = INF;
bfs();//5.BFS
if (ans != INF)printf("%dn", ans);//最后输出
else printf("Poor ANGEL has to stay in the prison all his life.n");
}
}

最后

以上就是狂野毛衣最近收集整理的关于地图类BFS模版（自用）的全部内容，更多相关地图类BFS模版（自用）内容请搜索靠谱客的其他文章。