广度优先搜索
如果我们把状态空间比作一张图，那么广度优先搜索就相当于对这张图的广度优先遍历
类似的，我们依然借助一个队列来实现广度优先搜索，起初队列中仅包含起始状态
在广度优先搜索的过程中，我们不断从队头取出状态，对于该状态面临的所有分支，把沿着每条分支到达的下一个状态（如果未访问过或者能够被更新成更优的解）插入队尾
重复执行上述过程直到队列为空
习题
立体推箱子
题目描述
立体推箱子是一个风靡世界的小游戏。
游戏地图是一个
行
列的矩阵，每个位置可能是硬地（用 . 表示）、易碎地面（用 E 表示）、禁地（用 # 表示）、起点（用 X 表示）或终点（用 O 表示）。
你的任务是操作一个
的长方体。
这个长方体在地面上有两种放置形式，“立”在地面上（
的面接触地面）或者“躺”在地面上（
的面接触地面）。
在每一步操作中，可以按上下左右四个键之一。
按下按键之后，长方体向对应的方向沿着棱滚动
度。
任意时刻，长方体不能有任何部位接触禁地，并且不能立在易碎地面上。
字符 X 标识长方体的起始位置，地图上可能有一个 X 或者两个相邻的 X。
地图上唯一的一个字符 O 标识目标位置。
求把长方体移动到目标位置（即立在 O 上）所需要的最少步数。
在移动过程中，X 和 O 标识的位置都可以看作是硬地被利用。
输入格式
输入包含多组测试用例。
对于每个测试用例，第一行包括两个整数
和
。
接下来
行用来描述地图，每行包括
个字符，每个字符表示一块地面的具体状态。
当输入用例 N=0，M=0 时，表示输入终止，且该用例无需考虑。
输出格式
每个用例输出一个整数表示所需的最少步数，如果无解则输出 Impossible。
每个结果占一行。
数据范围
输入样例：
代码语言：javascript复制7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0
输出样例：
代码语言：javascript复制10
解析
将箱子的三个摆放形式看做三个点，进行拆点 bfs 求最短路即可
思路不难，代码一百行，调的头疼
代码语言：javascript复制#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 510;
struct Node
{
int x, y, st; //0立，1横，2竖
bool operator == (const Node& t) const
{
return x == t.x && y == t.y && st == t.st;
}
};
int n, m;
char g[N][N];
int d[N][N][3];
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
Node st, ed;
bool valid(int x, int y) //边界判断
{
return x && x <= n && y && y <= m;
}
bool valid(Node t) //障碍判断
{
if (!valid(t.x, t.y)) return false;
if (g[t.x][t.y] == '#') return false;
if (t.st == 0 && g[t.x][t.y] == 'E') return false;
if (t.st == 1 && g[t.x][t.y - 1] == '#') return false;
if (t.st == 2 && g[t.x - 1][t.y] == '#') return false;
return true;
}
void init()
{
for (int i = 1; i <= n; i ) for (int j = 1; j <= m; j )
{
if (g[i][j] == 'O') ed = {i, j}, g[i][j] = '.';
else if (g[i][j] == 'X')
{
st = {i, j, 0};
g[i][j] = '.';
for (int k = 0; k < 4; k )
{
int x = i dx[k], y = j dy[k];
if (valid(x, y) && g[x][y] == 'X')
{
st = {x, y};
if (k & 1) st.st = 2;
else st.st = 1;
g[x][y] = '.';
}
}
}
}
}
const int nx[3][4] = {{0, 2, 0, -1}, {0, 1, 0, -1}, {0, 1, 0, -2}};
const int ny[3][4] = {{2, 0, -1, 0}, {1, 0, -2, 0}, {1, 0, -1, 0}};
const int ns[3][4] = {{1, 2, 1, 2}, {0, 1, 0, 1}, {2, 0, 2, 0}};
int bfs()
{
memset(d, -1, sizeof(d));
d[st.x][st.y][st.st] = 0;
queue<Node> q;
q.push(st);
while (q.size())
{
Node top = q.front(); q.pop();
for (int i = 0; i < 4; i )
{
Node next =
{
top.x nx[top.st][i],
top.y ny[top.st][i],
ns[top.st][i]
};
if (!valid(next)) continue;
if (~d[next.x][next.y][next.st]) continue;
d[next.x][next.y][next.st] = d[top.x][top.y][top.st] 1;
if (next == ed) return d[next.x][next.y][next.st];
q.push(next);
}
}
return -1;
}
int main()
{
while (scanf("%d%d", &n, &m), n || m)
{
for (int i = 1; i <= n; i ) scanf("%s", g[i] 1);
init();
int res = bfs();
if (~res) printf("%dn", res);
else puts("Impossible");
}
return 0;
}
矩阵距离
题目描述
给定一个
行
列的
矩阵
，
与
之间的曼哈顿距离定义为：
输出一个
行
列的整数矩阵
，其中：
输入格式
第一行两个整数
。
接下来一个
行
列的
矩阵，数字之间没有空格。
输出格式
一个
行
列的矩阵
，相邻两个整数之间用一个空格隔开。
数据范围
输入样例：
代码语言：javascript复制3 4
0001
0011
0110
输出样例：
代码语言：javascript复制3 2 1 0
2 1 0 0
1 0 0 1
解析
假设整个 01 矩阵只有一个 1，其余全是 0
则求所有点到 1 的最短距离，等价于求这个 1 到其他所有点的最短距离
于是就可以以 1 为起点做一遍 BFS 即可
对于任意 01 矩阵，求所有点到 1 的最短距离，等价于所有的 1 到其他所有点的最短距离
于是原问题就变成了多源点最短路问题，做一个超级源点或者一开始起点全部加入队列都可
代码语言：javascript复制#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, m;
int d[N][N];
char g[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool valid(int x, int y)
{
return x && x <= n && y && y <= m;
}
int bfs()
{
memset(d, -1, sizeof d);
queue<PII> q;
for (int i = 1; i <= n; i )
for (int j = 1; j <= m; j )
if (g[i][j] == '1')
q.push({i, j}), d[i][j] = 0;
while (q.size())
{
PII top = q.front(); q.pop();
for (int i = 0; i < 4; i )
{
int x = top.x dx[i], y = top.y dy[i];
if (!valid(x, y)) continue;
if (~d[x][y]) continue;
d[x][y] = d[top.x][top.y] 1;
q.push({x, y});
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ) scanf("%s", g[i] 1);
bfs();
for (int i = 1; i <= n; i )
{
for (int j = 1; j <= m; j )
{
printf("%d ", d[i][j]);
}
puts("");
}
return 0;
}
推箱子
题目描述
推箱子游戏相信大家都不陌生，在本题中，你将控制一个人把
个箱子到目的地。
给定一张
行
列的地图，用字符 . 表示空地，字符 # 表示墙，字符 S 表示人的起始位置，字符 B 表示箱子的起始位置，字符 T 表示箱子的目标位置。
求一种移动方案，使箱子移动的次数最少，在此基础上再让人移动的总步数最少。
方案中使用大写的 EWSN（东西南北）表示箱子的移动，使用小写的 ewsn（东西南北）表示人的移动。
输入格式
输入包含多个测试用例。
对于每个测试用例，第一行包括两个整数
。
接下来
行，每行包括
个字符，用以描绘整个
行
列的地图。
当样例为
时，表示输入终止，且该样例无需处理。
输出格式
对于每个测试用例，第一行输出 Maze # 测试用例的序号。
第二行输入一个字符串，表示推箱子的总体移动过程，若无解，则输出 Impossible.。
每个测试用例输出结束后输出一个空行。
若有多条路线满足题目要求，则按照 N、S、W、E 的顺序优先选择箱子的移动方向（即先上下推，再左右推）。
在此前提下，再按照 n、s、w、e 的顺序优先选择人的移动方向（即先上下动，再左右动）。
数据范围
输入样例：
代码语言：javascript复制1 7
SB....T
1 7
SB..#.T
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
8 4
....
.##.
.#..
.#..
.#.B
.##S
....
###T
0 0
输出样例：
代码语言：javascript复制Maze #1
EEEEE
Maze #2
Impossible.
Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN
Maze #4
swwwnnnnnneeesssSSS
解析
首先这题拆点拆不了，如果把人和箱子的坐标都记录下来，则拆点后的距离也是多关键字：
但是这就出现了一个问题，BFS 每次扩展时，可能是箱子距离 1，可能是人的距离 1，还有可能是两者都 1
这就破坏了 BFS 辅助队列的单调性，即如果当前队列中被更新的状态符合单调性，但是队尾相对队头是两者都 1，如果此时队头元素又更新出来一个只有二者其中之一 1 的状态，此时是无法插入队尾了，于是就破坏了辅助队列的单调性
这种情况比较常见的就是，边权不是全 1 时的图最短路问题，解决方法是转而用堆来存储状态，也就是 BFS 变 Dijkstra
如果本题我们也考虑用堆来作为辅助，则每轮操作会多一个
，计算一下时间复杂度：
时间复杂度直接拉满，本题又是多样例，故肯定会超时，考虑其他解法
蓝书上给出了非常漂亮的做法：双重BFS
每推一次箱子所要经历的步骤：人先移动到箱子的一侧，箱子再向着人的反向移动，人最后取代箱子的位置
则 BFS 的状态存储就可以用三元组完成：
，其中
是箱子坐标，
是人位于箱子四相邻的方向
每次从队头取出一个元素后，进行状态更新的步骤如下：
- 箱子在
不动，人用尽量少的步数从起点
移动到终点
，且中途不能经过
- 人沿着
方向推一次箱子，箱子移动到
，人移动到
- 将新状态入队，并且把箱子移动步数
和人移动步数
更新
该双重BFS在每一轮中做了两次BFS，为了代码格式养眼，调试方便，考虑将两次 BFS 处理成两个模块调用
输出方案就很简单，对于已有的状态数组，以及目标状态，进行一波倒推即可
代码语言：javascript复制#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 25;
struct Node
{
int x, y, dir;
};
int n, m;
char g[N][N];
bool stman[N][N];
PII dist[N][N][4];
vector<int> path[N][N][4];
Node pre[N][N][4];
bool valid(int x, int y)
{
return x && x <= n && y && y <= m && g[x][y] != '#';
}
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
int bfs_man(PII start, PII end, PII box, vector<int> &seq)
{
static int pre[N][N];
memset(pre, -1, sizeof(pre));
memset(stman, 0, sizeof(stman));
stman[start.x][start.y] = true;
stman[box.x][box.y] = true;
queue<PII> q;
q.push({start.x, start.y});
while (q.size())
{
PII top = q.front(); q.pop();
if (end == top)
{
for (int x = top.x, y = top.y; ~pre[x][y]; )
{
int d = pre[x][y];
seq.push_back(d);
x = x dx[d ^ 1], y = y dy[d ^ 1];
}
return seq.size();
}
for (int i = 0; i < 4; i )
{
int x = top.x dx[i], y = top.y dy[i];
if (valid(x, y) && !stman[x][y])
{
pre[x][y] = i;
stman[x][y] = true;
q.push({x, y});
}
}
}
return -1;
}
bool bfs(Node& end)
{
memset(dist, -1, sizeof(dist));
memset(pre, -1, sizeof(pre));
//find the people position and intialize the point
PII stm, stb;
for (int i = 1; i <= n; i )
for (int j = 1; j <= m; j )
if (g[i][j] == 'S') stm = {i, j}, g[i][j] = '.';
else if (g[i][j] == 'B') stb = {i, j}, g[i][j] = '.';
//insert the start point into the bfs auxiliary queue
queue<Node> q;
for (int i = 0; i < 4; i )
{
int x = stb.x - dx[i], y = stb.y - dy[i];
if (!valid(x, y)) continue;
vector<int> seq;
int cnt = bfs_man(stm, {x, y}, stb, seq);
if (cnt != -1)
{
//for (auto it: seq) cout << it << " "; cout << endl;
dist[stb.x][stb.y][i] = {0, cnt};
path[stb.x][stb.y][i] = seq;
q.push({stb.x, stb.y, i});
}
}
PII res = {1e9, 1e9};
bool flag = false;
while (q.size())
{
Node top = q.front(); q.pop();
//printf("man:%d %d box:%d %d dir:%dn", top.x - dx[top.dir], top.y - dy[top.dir], top.x, top.y, top.dir);
// check the end
if (g[top.x][top.y] == 'T')
{
flag = true;
if (res > dist[top.x][top.y][top.dir])
{
res = dist[top.x][top.y][top.dir];
end = top;
}
continue;
}
PII man_pos = {top.x - dx[top.dir], top.y - dy[top.dir]}; //position the man locates
//find other trans path
for (int k = 0; k < 4; k )
{
int bx = top.x dx[k], by = top.y dy[k]; //the goal of the box
int px = top.x - dx[k], py = top.y - dy[k]; //the position man need to reach
if (!valid(px, py) || !valid(bx, by)) continue;
//try to push the box
vector<int> seq;
int cnt = bfs_man(man_pos, {px, py}, {top.x, top.y}, seq);
if (cnt != -1) //cal the distance
{
PII temp = {dist[top.x][top.y][top.dir].x 1, dist[top.x][top.y][top.dir].y cnt};
if (dist[bx][by][k].x == -1)
{
pre[bx][by][k] = top;
path[bx][by][k] = seq;
dist[bx][by][k] = temp;
q.push({bx, by, k});
}
else if (dist[bx][by][k] > temp)
{
pre[bx][by][k] = top;
path[bx][by][k] = seq;
dist[bx][by][k] = temp;
}
}
}
}
//cout << end.x << " " << end.y << endl;
return flag;
}
int main()
{
int T = 1;
while (scanf("%d%d", &n, &m), n || m)
{
printf("Maze #%dn", T );
for (int i = 1; i <= n; i ) scanf("%s", g[i] 1);
Node end;
if (!bfs(end)) puts("Impossible.");
else
{
char ops[] = {"nswe"};
string res;
while (pre[end.x][end.y][end.dir].dir != -1)
{
//cout << end.x << " " << end.y << " " << end.dir << endl;
res = ops[end.dir] - 32;
for (auto dir: path[end.x][end.y][end.dir]) res = ops[dir];
end = pre[end.x][end.y][end.dir];
}
if (path[end.x][end.y][end.dir].size())
for (auto dir: path[end.x][end.y][end.dir]) res = ops[dir];
reverse(res.begin(), res.end());
cout << res << endl;
}
puts("");
}
return 0;
}
