BFS专题5 跨步迷宫

原创于 2023-09-25 09:38:31 发布 · 粉丝可见 · 151 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/133266456

题目：

样例1：

`cobol<br/>3 3<br/>0 1 0<br/>0 0 0<br/>0 1 0<br/>`

3

样例2：

`cobol<br/>3 3<br/>0 1 0<br/>0 1 0<br/>0 1 0<br/>`

-1

思路：

这里的跨步迷宫，我们可以将移动坐标扩大一倍，即加上 {2,-2,0,0 }的移动坐标即可，特别需要注意的是，我们得到某个坐标后对它 / 2 判断该坐标是否可以走动，至于为什么要这样做，因为 这样就可以判断跨步或者不跨步是否可以走动的条件。

代码详解如下：

#include <bits/stdc++.h>
#define endl '\n'
#define x first
#define y second
#define mk make_pair
#define umap unordered_map
#define ___G cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
using namespace std;
const int N = 500 + 10;
using PII = pair<int,int>;
int n,m;
int g[N][N];	// 迷宫图
bool vis[N][N];	// 标记是否走动过

// 移动坐标 
int dx[8] = {1,-1,2,-2,0,0,0,0};
int dy[8] = {0,0,0,0,1,-1,2,-2};

// 判断走动条件 
inline bool isRun(int x,int y)
{
	return (x >= 0 && x < n && y >= 0 && y < m && !g[x][y] && !vis[x][y]);
}

inline int BFS(int x,int y)
{
	int step = 0;
	// 存储走动坐标 
	queue<PII>q;
	// 存储起点 并标记 
	q.push(mk(x,y));
	vis[x][y] = true;
	
	// 开始 BFS 走动 
	// 这一层是走动的每一步 
	while(q.size())
	{
		int sz = q.size();
		// 这一层是判断走动的方向 
		while(sz--)
		{
			// 开始取出存储的走动坐标 
			auto now = q.front();
			q.pop();
			// 如果当前坐标走到了出口，返回步数 
			if(now.x == n - 1 && now.y == m - 1)
			{
				return step;
			}
			// 标记当前坐标 
			vis[now.x][now.y] = true;
			
			// 判断走动的方向 
			for(int i = 0;i < 8;++i)
			{
				// bx 和 by 是走动第一步下一个坐标 
				int bx = now.x + dx[i];
				int by = now.y + dy[i];
				
				// tx 和 ty 是跨步的判断，
				// 这里 dx[i] / 2 有效的避免了数组越界
				int tx = now.x + (dx[i]>>1);
				int ty = now.y + (dy[i]>>1);
				
				// 如果可以走动第一步，并且也可以跨步 
				if(isRun(bx,by) && !g[tx][ty])
				{
					// 存储该坐标 并标记 
					q.push(mk(bx,by)); 
					vis[bx][by] = true;
				} 
			}
		}	
		// 开始走动累加步数 
		++step;
	}
	
	// 如果无法到达终点，返回 -1 
	return -1;
}

inline void solve()
{
	cin >>n >>m;
	for(int i = 0;i < n;++i)
	{
		for(int j = 0;j < m;++j)
		{
			cin >> g[i][j];
		}
	}
	
	cout << BFS(0,0) <<endl;
}

signed main()
{
	___G;
//	freopen("a.txt","r",stdin);
	int _t = 1;
	//cin >> _t;
	while(_t--)
	{
		solve();
	}


	return 0;
}