Atcoder - abc176 -- D - Wizard in Maze【BFS + 双端队列】

题意

给定一个地图，有起点和终点。现在有两种移动方法：
1.上下左右移动；
2.使用魔法，可以向(以当前为中心的位置5 x 5的正方形内的广场)移动。
问从起点到终点至少需要使用多少次魔法，如果不能到达则输出-1.

思路

如果一条路可以通过第一种方式到达，那就尽量不采用第二种方法，如果不没有达到终点，那么就用第二种方法从第一种方法走的所有路中探索没有走过的路，如果能达到终点，那么输出最小使用的魔法次数，如果不能那么输出-1。
根据上面的思路，我们可以采用双端队列 + bfs来操作，将第一种移动方法走的路压入队列前端，第二种移动方法压入队列后端，如果第一种方法走的路在队列中没有了且没达到终点，就开始使用魔法。

AC代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<utility>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
#define IOS ios::sync_with_stdio(false)
#define x first
#define y second 
const int maxn = 1e3 + 5;
char mp[maxn][maxn];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int path[maxn][maxn], n, m;
bool vis[maxn][maxn];
pii st, en;
int bfs(){
	deque<pii>	q;
	memset(path, -1, sizeof(path));
	q.push_front(st);
	path[st.x][st.y] = 0;
	while (!q.empty()){
		pii now = q.front(); q.pop_front();
		if (now.x == en.x && now.y == en.y)	return path[now.x][now.y];
		for (int i = 0; i < 4; ++i){
			int dx = now.x + dir[i][0];
			int dy = now.y + dir[i][1];
			//此路没有被走过，或者有更短的路径。
			if (mp[dx][dy] == '.' && (path[dx][dy] == -1 || path[dx][dy] > path[now.x][now.y])){
				path[dx][dy] = path[now.x][now.y];
				q.push_front(pii(dx, dy));
			}
		}
		// 枚举以当前坐标为中心的5 * 5正方形内的路。
		for (int dx = now.x - 2; dx <= now.x + 2; ++dx){
			for (int dy = now.y - 2; dy <= now.y + 2; ++dy){
				if (dx < 1 || dy < 1 || dx > n || dy > m)	continue;
				//这条路没有被走过
				if (mp[dx][dy] == '.' && path[dx][dy] == -1){
					path[dx][dy] = path[now.x][now.y] + 1;
					q.push_back(pii(dx, dy));
				}
			}
		}
	}
	return -1;
}
void solve(){
	cin >> n >> m;
	cin >> st.x >> st.y;
	cin >> en.x >> en.y;
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j){
			cin >> mp[i][j];
		}
	}
	cout << bfs() << endl;
}
int main(){
	IOS;
	solve();
	return 0;
}

本文地址：https://blog.csdn.net/qq_45249273/article/details/108186465