844. 走迷宫 - AcWing
题面:
给定一个 \(n×m\) 的二维整数数组,用来表示一个迷宫,数组中只包含 \(0\) 或 \(1\),其中 \(0\) 表示可以走的路,\(1\) 表示不可通过的墙壁。
最初,有一个人位于左上角 \((1,1)\) 处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问,该人从左上角移动至右下角 \((n,m)\) 处,至少需要移动多少次。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
typedef pair<int, int> PII;
int n, m;
int s[N][N]; //地图
int p[N][N]; //每点距离起点的最短路径长度
queue<PII> q; //记录每一步走到的点
int d[][4] = { {-1,0,1,0},{0,1,0,-1} }; //方向
int bfs() {
q.push({ 0,0 }); //起点(0,0)入队
while (!q.empty()) { //每次外循环取出的点都为同一步数
PII tmp = q.front();
q.pop();
for (int i = 0; i < 4; i++) { //枚举四个方向
int x = tmp.first + d[0][i];
int y = tmp.second + d[1][i];
//若这个点能走到,即未超地图范围、无障碍物且未走过
if (x >= 0 && x < n && y >= 0 && y < m && !s[x][y] && !p[x][y]) {
p[x][y] = p[tmp.first][tmp.second] + 1;
q.push({ x,y });
}
}
}
return p[n - 1][m - 1];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> s[i][j];
cout << bfs() << endl;
}
845. 八数码 - AcWing
题面:
在一个 \(3×3\) 的网格中,\(1∼8\) 这 \(8\) 个数字和一个 \(x\) 恰好不重不漏地分布在这 \(3×3\) 的网格中。
在游戏过程中,可以把 \(x\) 与其上、下、左、右四个方向之一的数字交换(如果存在)。
我们的目的是通过交换,使得网格变为如下排列(称为正确排列):
1 2 3
4 5 6
7 8 x
现在,给你一个初始网格,请你求出得到正确排列至少需要进行多少次交换。
基本思路:[1]
- 穷举通过交换能得到的序列,保存交换次数。过程中,如果出现了结果序列,就输出交换次数。
- 序列保存用
queue
,交换次数保存用unordered_map
。
注意点:
- Q:为什么
h[tmp] = path + 1;
不能改为h[tmp]++
? - A:因为
path
中的h[tmp]
保存的是上一次序列,而小循环内的已经经过了swap
,为新序列,会导致交换次数更新失败,所有的序列交换次数都为1。
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
const int N = 105;
typedef pair<int, int> PII;
string str; //初始序列
queue<string> q; //记录每一次交换后的序列
unordered_map<string, int> h; //记录序列与对应交换次数
int d[][4] = { {-1,0,1,0},{0,1,0,-1} }; //方向
int bfs() {
q.push(str);
h[str] = 0;
while (!q.empty()) {
string tmp = q.front();
q.pop();
if (tmp == "12345678x")
return h[tmp];
int pos = tmp.find('x');
int path = h[tmp];
for (int i = 0; i < 4; i++) {
//一维转换为二维坐标
int x = pos / 3 + d[0][i];
int y = pos % 3 + d[1][i];
if (x >= 0 && x < 3 && y >= 0 && y < 3) {
swap(tmp[pos], tmp[3 * x + y]);
//当前序列若为首次出现,则记录
if (h.find(tmp) == h.end()) {
h[tmp] = path + 1;
q.push(tmp);
}
swap(tmp[pos], tmp[3 * x + y]); //恢复现场,枚举下一个方向
}
}
}
return -1;
}
int main()
{
for (int i = 0; i < 9; i++) {
char c;
cin >> c;
str += c;
}
cout << bfs() << endl;
}