当边权为1时候，用bfs解决最短路问题
题目：
走迷宫
给定一个 n×m的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8思路：
从起点开始，往前走第一步，记录下所有第一步能走到的点，然后从所第一步能走到的点开始，往前走第二步，记录下所有第二步能走到的点，重复下去，直到走到终点。输出步数即可。
这就是广度优先遍历的思路。
用 g 存储地图，f存储起点到其他各个点的距离。
从起点开始广度优先遍历地图。
当地图遍历完，就求出了起点到各个点的距离，输出f[n][m]即可。
代码：
void bfs(int a, int b): 广度优遍历函数。输入的是起点坐标。
queue<PII> q;:用来存储每一步走到的点。
while(!q.empty())循环：循环依次取出同一步数能走到的点，再往前走一步。
int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};:一个点往下一步走得时候，可以往上下左右四方向走。
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N];//存储地图
int f[N][N];//存储距离
int n, m;
void bfs(int a, int b)//广度优先遍历
{
queue<PII> q;
q.push({a, b});
//初始点的距离为 0.
//可以不要这一句，因为f初始化的时候，各个点为0
f[0][0] = 0;
while(!q.empty())
{
PII start = q.front();
q.pop();
//这一句可以不要，因为入队的时候就置为了1
g[start.first][start.second] = 1;
int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
for(int i = 0; i < 4; i++)//往四个方向走
{
//当前点能走到的点
int x = start.first + dx[i], y = start.second + dy[i];
//如果还没有走过
if(g[x][y] == 0)
{
//走到这个点，并计算距离
g[x][y] = 1;
f[x][y] = f[start.first][start.second] + 1;//从当前点走过去，则距离等于当前点的距离+1.
//这个点放入队列，用来走到和它相邻的点。
q.push({x, y});
}
}
}
cout << f[n][m];
}
int main()
{
memset(g, 1, sizeof(g));
cin >> n >>m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> g[i][j];
}
}
bfs(1,1);
}
、进阶：
八数码
在一个 3×3的网格中，1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。
例如：
1 2 3
x 4 6
7 5 8
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 x
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将 3×3的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出 −1。
输入样例：
2 3 4 1 5 x 7 6 8
输出样例
19思路：
起始状态： 为 1 2 3 x 4 6 7 5 8
交换一次：
x 与上方元素交换得到： x 2 3 1 4 6 7 5 8
x 与右方元素交换得到： 1 2 3 4 x 6 7 5 8
x 与下方元素交换得到： 1 2 3 7 4 6 x 5 8
交换两次得到：
2 x 3 1 4 6 7 5 8
1 x 3 4 2 6 7 5 8
1 2 3 4 6 x 7 5 8
1 2 3 4 5 6 7 x 8
1 2 3 7 4 6 5 x 8
交换三次得到：
2 3 x 1 4 6 7 5 8
.....
1 2 3 4 5 6 7 8 x
.....
得到了最终结果，输出 3.
算法思路
用一个队列保存当前获得的序列
用一个哈希表保存各个序列与对应额交换次数。
从队列中取出队头这个序列，计算出这个序列通过交换能得到的序列。如果能到得的序列是个新序列（哈希表中没有这个序列），就把这个新序列放入队尾，哈希表中记录新序列对应的交换次数。
如果在上述过程中得到了结果序列，则输出交换次数，结束。
如果最终没有得到结果序列。输出-1。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
// 保存各个序列
queue<string> q;
string s;
// 保存序列与对应的交换次数
unordered_map<string, int> h;
int main()
{
// 输入原始序列
for(int i = 1; i <= 9; i++)
{
char c;
cin >> c;
s += c;
}
// 保存初始状态
h[s] = 0;
q.push(s);
// 定义上下左右四个交换方向
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
// 依次进行交换
while(!q.empty())
{
// 获得当前序列
string t = q.front();
q.pop();
// 如果是最后结果，输出答案
if(t == "12345678x")
{
cout << h[t] << endl;
return 0;
}
// 找到 x 的位置
int pos = t.find('x');
// 计算 x 的坐标
int a = pos /3 , b = pos % 3 ;
// 获取当前序列对应的交换次数
int dist = h[t];
// 尝试和四个方向的元素进行交换
for(int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
// 判断是否越界
if(x >= 0 && x <= 2 && y >= 0 && y <= 2)
{
// 交换
swap(t[pos], t[3 * x + y]);
// 如果是个新序列，就保存新序列和对应的交换次数
if(h.find(t) == h.end())
{
h[t] = dist + 1;
q.push(t);
}
// 恢复现场，进行下一个方向的交换
swap(t[pos], t[3 * x + y]);
}
}
}
// 没有得到结果序列，输出-1
cout << -1;
return 0;
}
代码难点：
1. if(h.find(t) == h.end())
解 ：
如果在unordered_map中找不到t，就会固定返回h.end()，即它是新增的字符串；
2. 一维坐标映射到二维 -> (x / n, x % n )
二维映射一维 -> x * n + y