---

题号1577 E.迷宫plus （有趣的BFS练习）

原创 已于 2023-11-01 14:23:38 修改 · 粉丝可见 · 166 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/134160376

题目：

样例：

cobol<br/>1<br/>5 5<br/>LRLRL<br/>LLLLL<br/>RRRRR<br/>UUUUU<br/>UUUUD<br/>

4

思路：

一般遇到坐标迷宫，基本上都是DFS或者 BFS ，这里多了一个条件就是要最少修改操作数，所以我们DFS很难控制这一条件，通过 BFS 搜索，利用BFS常用的队列改成优先队列形式搜索即可，优先最少修改的操作数坐标我们往该坐标上走动即可。

代码详解如下：

#include <iostream>
#include <queue>
#include <cstring>
#define endl '\n'
#define x first
#define y second
#define int long long
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1000;
 
using PII = pair<int,int>;	// 定义变量名坐标对组
 
int n,m;
string g[N];	// 迷宫图
 
PII r[N];	// 存储对应字符的移动操作坐标变化
 
string Move = "LRUD";// 移动操作
 
bool st[N][N];	// 标记是否走动过当前坐标，对应题目中的“到达后门又关上“
 
// 坐标结构体
struct Coord
{
	int x,y;	// 坐标
	int cnt;	// 计数修改次数
	
	// 构造结构体函数
	inline Coord(int _x,int _y,int _cnt):x(_x),y(_y),cnt(_cnt){}
	
	// 重载比较符，定义排序规则，优先修改次数少的坐标
	// 我们向那个坐标走
	inline bool operator<(const Coord&t)const
	{
		return cnt > t.cnt;
	}
};
 
// 判断是否可以走动的条件
inline bool isRun(Coord& next)
{
	int x = next.x,y = next.y;
	return (x >= 0 && x < n && y >= 0 && y < m && !st[x][y]);
}
 
// 重载 + 运算符，方便我们结构体坐标累加变化
inline Coord operator+(Coord&a,PII&b)
{
	return Coord(a.x + b.x,a.y + b.y,a.cnt);
}
 
inline int BFS()
{
	// 优先队列,存储走动的坐标计划
	priority_queue<Coord>q;
	
	// 存储起点，和操作次数的状态
	q.emplace(Coord(0,0,0));
	
	// 开始 BFS 搜索
	while(q.size())
	{
		// 获取当前走动到的坐标
		Coord now = q.top();
		q.pop();
		
		st[now.x][now.y] = true;	// 关上后面，即标记坐标
		
		// 如果到达了迷宫出口，输出最少操作数
		if(now.x == n - 1 && now.y == m - 1)
		{
			return now.cnt;
		}
		
		// 对每一个移动操作搜索是否可行
		for(int i = 0;i < 4;++i)
		{
			char op = Move[i];	// 获取操作的字符
			
			Coord next = now + r[op];	// 更新操作后的当前坐标
			
			// 判断是否符合走动条件
			if(isRun(next))
			{
				// 如果可以走动,该操作等于当前迷宫格子的操作符
				// 那么不用计数修改操作数，反之 修改操作数 + 1
				if(g[now.x][now.y] == op) q.emplace(Coord(next.x,next.y,next.cnt));
				else q.emplace(Coord(next.x,next.y,next.cnt + 1));
			}
		}
	}
	// 给个返回值，如果走不出出口返回-1
	return -1;	
}
 
inline void solve()
{
	
	// 清空上一个样例所标记的
	memset(st,false,sizeof st);
	
	// 输入各种信息
	cin >> n >> m;
	for(int i = 0;i < n;++i)
	{
		cin >> g[i];
	}
	
	//输出答案
	cout << BFS() << endl;
	
}
 
signed main()
{
//	freopen("a.txt", "r", stdin);
	
	// 标记对应的操作方向，坐标变化
	r['L'] = PII(0,-1);
	r['R'] = PII(0,1);
	r['U'] = PII(-1,0);
	r['D'] = PII(1,0);
	
	IOS;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}

最后提交：