搜索 - 广度优先搜索(BFS)普通模板

bfs广度优先搜索模板

本人蒟蒻，为响应号召写下bfs模板一篇可以适用于求最短步数，等最优解问题。如有不足或者不对的地方请各位大佬及时指出 ^- 欢迎来戳

具体实现代码(C++)

各个模块功能和简单明了

#include <iostream>

#include <queue>

#include <algorithm>

#define N 100

using namespace std;

int n, m;

int  map[N][N];

bool vis[N][N];

//一般情况下的方向数组 具体的视情况列方向数组

int  dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; //方向数组

struct node{

	int x;

	int y;

	int step; //可以记录最小步数之类的最优解

	node(int x, int y ,int step) :x(x), y(y),step(step) { }

	node(){ }

};

//判断是否在图中

bool inmap(int x, int y)

{

	if (x >= 1 && x <= n && y >= 1 && y <= m)return true;

	else return false;

}

void bfs(int sx, int sy)

{

	vis[sx][sy] = 1; //标注起始点

	queue<node> q;

	q.push(node(sx, sy ,0));

	while (!q.empty())

	{

		node now = q.front();

		for (int i = 0; i < 4; i++)

		{

			int x = now.x + dir[i][0];

			int y = now.y + dir[i][1];

			int step = now.step + 1;  //一次只走一步

			if (inmap(x, y) == true && vis[x][y] == false)

			{

				//此处还可以进行别的剪枝

				//可以是多个条件剪枝或者终止条件由具体题目而定

				if (到达终点或者是其他剪枝操作)

				{

					//进行最后处理其他剪枝操作....

					return;

				}

				else {

					vis[x][y] = 1; //标记该点已经来过并将其放入队列

					q.push(node(x, y,step + 1));

				}

			}

			else return;

		}

		q.pop();

	}

	return;

}

void init()

{

	int sx, sy;

	cin >> n >> m >> sx >> sy;

	bfs(sx, sy);

}

int main()

{

	init();

	system("pause");

	return 0;

}

巴特西

搜索 - 广度优先搜索(BFS)普通模板

bfs广度优先搜索模板

具体实现代码(C++)

最新文章

热门文章