一、理解与感悟
-
(bfs)适合寻找最短(最长)的路径，因为是按层一层层找的，第一个符合条件的就是最短的路径。
-
走迷宫一般使用(dx),(dy),就是左上右下，或者上右下左的二组变量常数，在蛇形排列中，还强调了四个方向的初始化方向，在走迷宫时，不强调顺序，哪个方向先来都是一样的。
-
距离数组一般初始化为(-1)，表示未探索的位置。有时其它题中也表示不可以走的墙，具体问题再具体分析。
memset(d,-1,sizeof d);
二、bfs解法
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N]; // 保存的是地图(空地与墙)
int d[N][N]; // 每个节点到入口的距离
//delta向量
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int bfs() {
queue<PII> q;
//第一个点
q.push({0, 0});
//赋值初始值-1, 注意这里是二维数组的初始化,表示所有的点都没有走过
memset(d, -1, sizeof d);
d[0][0] = 0;//表示这个出发点走过了,就是第0步
while (!q.empty()) {
//第一个到达终点的就停止
if (d[n - 1][m - 1] > -1) break;
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = t.first + dx[i], y = t.second + dy[i];
//不出界，并且是空地(不是墙)可以走 且之前没有走过
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
d[x][y] = d[t.first][t.second] + 1;
q.push({x, y});
}
}
}
return d[n - 1][m - 1];
}
int main() {
//读入优化
ios::sync_with_stdio(false);
//读入地图
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
//宽度优先搜索
cout << bfs() << endl;
return 0;
}
三、bfs带路径
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N]; // 保存的是地图(空地与墙)
int d[N][N]; // 每个节点到入口的距离
queue<PII> q;
PII Prev[N][N];//记录每个节点是从哪个节点过来的
//delta向量
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int bfs() {
//第一个点
q.push({0, 0});
//赋值初始值-1, 注意这里是二维数组的初始化,表示所有的点都没有走过
memset(d, -1, sizeof d);
d[0][0] = 0;//表示这个出发点走过了
while (!q.empty()) {
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = t.first + dx[i], y = t.second + dy[i];
//不出界，并且是空地(不是墙)可以走 且之前没有走过
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
d[x][y] = d[t.first][t.second] + 1;
//x，y这个点是来自哪个点
Prev[x][y] = t;
q.push({x, y});
}
}
}
//输出路径
stack<PII> s1; //利用一个栈，把路径掉过来
int x = n - 1, y = m - 1; //出口
while (x || y) {
s1.push({x, y});
auto t = Prev[x][y];
x = t.first, y = t.second;
}
//加入出发节点
s1.push({0, 0});
while (!s1.empty()) {
auto t = s1.top();
cout << t.first << ' ' << t.second << endl;
s1.pop();
}
return d[n - 1][m - 1];
}
int main() {
//读入优化
ios::sync_with_stdio(false);
//读入地图
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
//宽度优先搜索
cout << bfs() << endl;
return 0;
}
四、dfs带路径
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N]; // 保存的是地图(空地与墙)
//delta向量
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
vector<PII> res;
vector<vector<PII>> finalRes;
void dfs(int x, int y) {
//1、是否完成迷宫，收集结果
if (x == n - 1 && y == n - 1) {
//保存下来，用来找哪条路最短
finalRes.push_back(res);
return;
}
//2、遍历当前所有可能
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
//不出界，并且是空地(不是墙)可以走 且之前没有走过
if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == 0) {
//标识使用过
g[nx][ny] = 1;
//加入路径
res.push_back({nx, ny});
//递归
dfs(nx, ny);
//恢复现场，回溯
g[nx][ny] = 0;
//弹出路径
res.pop_back();
}
}
}
int main() {
//读入优化
ios::sync_with_stdio(false);
//读入地图
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
//深度优先搜索
dfs(0, 0);
int minSize = INT32_MAX;
int whiceId = -1;
for (int i = 0; i < finalRes.size(); i++) {
if (finalRes[i].size() < minSize) {
minSize = finalRes[i].size();
whiceId = i;
}
}
cout << finalRes[whiceId].size() << endl;
for (int i = 0; i < finalRes[whiceId].size(); i++)
cout << finalRes[whiceId][i].first << " " << finalRes[whiceId][i].second << endl;
return 0;
}