文章

105

粉丝

69

获赞

117

访问

54.0k

头像
迷宫(C++11 bfs宽搜 附详细注释) 题解:

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int  N = 110;
int n, m;
char g[N][N]; //存图
int d[N][N]; //存每个点最短距离
//四个方向偏移量
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
//bfs宽搜
int bfs(int x1, int y1)
{
	queue<PII> q; //pair数据类型的队列
	
	d[x1][y1] = 0;//初始化起点为0
	q.push({x1, y1}); //存起点的坐标
	
	while(q.size())
	{
		auto t = q.front();
		q.pop(); //搜完每个点注意弹出
		
		int a = t.first, b = t.second;
		for(int i = 0; i < 4; i ++) //枚举四个方向
		{
			int x = a + dx[i], y = b + dy[i];
			
			if(g[x][y] == 'E') return d[a][b] + 1; //搜到终点直接返回答案
			//边界和搜索条件
			if(x > 0 && y > 0 && x <= n && y <= m && d[x][y] == -1 && g[x][y] == '*')
			{
				d[x][y] = d[a][b] + 1; //更新*到S距离
				q.push({x, y}); //将上下左右扩展的*的坐标加入队列中
			}
		}
	}
	
	return -1; //没搜到E就返回-1
}

int main()
{
	while(cin >> n >> m, n, m)
	{
		memset(d, -1, sizeof d); //每次数据距离初始...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发