如何用 BFS 算法秒杀各种智力题
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 773. Sliding Puzzle | 773. 滑动谜题 | 🔴 |
———–
滑动拼图游戏大家应该都玩过，下图是一个 4x4 的滑动拼图：
拼图中有一个格子是空的，可以利用这个空着的格子移动其他数字。你需要通过移动这些数字，得到某个特定排列顺序，这样就算赢了。
我小时候还玩过一款叫做「华容道」的益智游戏，也和滑动拼图比较类似：
实际上，滑动拼图游戏也叫数字华容道，你看它俩挺相似的。
那么这种游戏怎么玩呢？我记得是有一些套路的，类似于魔方还原公式。但是我们今天不来研究让人头秃的技巧，这些益智游戏通通可以用暴力搜索算法解决，所以今天我们就学以致用，用 BFS 算法框架来秒杀这些游戏。
一、题目解析
力扣第 773 题「 滑动谜题」就是这个问题，题目的要求如下：
给你一个 2x3 的滑动拼图，用一个 2x3 的数组 board 表示。拼图中有数字 0~5 六个数，其中数字 0 就表示那个空着的格子，你可以移动其中的数字，当 board 变为 [[1,2,3],[4,5,0]] 时，赢得游戏。
请你写一个算法，计算赢得游戏需要的最少移动次数，如果不能赢得游戏，返回 -1。
比如说输入的二维数组 board = [[4,1,2],[5,0,3]]，算法应该返回 5：
如果输入的是 board = [[1,2,3],[5,4,0]]，则算法返回 -1，因为这种局面下无论如何都不能赢得游戏。
二、思路分析
对于这种计算最小步数的问题，我们就要敏感地想到 BFS 算法。
这个题目转化成 BFS 问题是有一些技巧的，我们面临如下问题：
1、一般的 BFS 算法，是从一个起点 start 开始，向终点 target 进行寻路，但是拼图问题不是在寻路，而是在不断交换数字，这应该怎么转化成 BFS 算法问题呢？
2、即便这个问题能够转化成 BFS 问题，如何处理起点 start 和终点 target？它们都是数组哎，把数组放进队列，套 BFS 框架，想想就比较麻烦且低效。
首先回答第一个问题，BFS 算法并不只是一个寻路算法，而是一种暴力搜索算法，只要涉及暴力穷举的问题，BFS 就可以用，而且可以最快地找到答案。
你想想计算机怎么解决问题的？哪有什么特殊技巧，本质上就是把所有可行解暴力穷举出来，然后从中找到一个最优解罢了。
明白了这个道理，我们的问题就转化成了：如何穷举出 board 当前局面下可能衍生出的所有局面？这就简单了，看数字 0 的位置呗，和上下左右的数字进行交换就行了：
这样其实就是一个 BFS 问题，每次先找到数字 0，然后和周围的数字进行交换，形成新的局面加入队列…… 当第一次到达 target 时，就得到了赢得游戏的最少步数。
对于第二个问题，我们这里的 board 仅仅是 2x3 的二维数组，所以可以压缩成一个一维字符串。其中比较有技巧性的点在于，二维数组有「上下左右」的概念，压缩成一维后，如何得到某一个索引上下左右的索引？
对于这道题，题目说输入的数组大小都是 2 x 3，所以我们可以直接手动写出来这个映射：
// 记录一维字符串的相邻索引
int[][] neighbor = new int[][]{
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 记录一维字符串的相邻索引
int neighbor[6][3] = {
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
# 记录一维字符串的相邻索引
neighbor = [
[1, 3],
[0, 4, 2],
[1, 5],
[0, 4],
[3, 1, 5],
[4, 2]
]
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 记录一维字符串相邻索引
neighbor := [][]int{
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2},
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 记录一维字符串的相邻索引
var neighbor = [
[1, 3],
[0, 4, 2],
[1, 5],
[0, 4],
[3, 1, 5],
[4, 2]
];
这个含义就是，在一维字符串中，索引 i 在二维数组中的的相邻索引为 neighbor[i]：
那么对于一个 m x n 的二维数组，手写它的一维索引映射肯定不现实了，如何用代码生成它的一维索引映射呢？
观察上图就能发现，如果二维数组中的某个元素 e 在一维数组中的索引为 i，那么 e 的左右相邻元素在一维数组中的索引就是 i - 1 和 i + 1，而 e 的上下相邻元素在一维数组中的索引就是 i - n 和 i + n，其中 n 为二维数组的列数。
这样，对于 m x n 的二维数组，我们可以写一个函数来生成它的 neighbor 索引映射：
int[][] generateNeighborMapping(int m, int n) {
int[][] neighbor = new int[m * n][];
for (int i = 0; i < m * n; i++) {
List<Integer> neighbors = new ArrayList<>();
// 如果不是第一列，有左侧邻居
if (i % n != 0) neighbors.add(i - 1);
// 如果不是最后一列，有右侧邻居
if (i % n != n - 1) neighbors.add(i + 1);
// 如果不是第一行，有上方邻居
if (i - n >= 0) neighbors.add(i - n);
// 如果不是最后一行，有下方邻居
if (i + n < m * n) neighbors.add(i + n);
// Java 语言特性，将 List 类型转为 int[] 数组
neighbor[i] = neighbors.stream().mapToInt(Integer::intValue).toArray();
}
return neighbor;
}
至此，我们就把这个问题完全转化成标准的 BFS 问题了，借助前文 BFS 算法框架 的代码框架，直接就可以套出解法代码了：
class Solution {
public int slidingPuzzle(int[][] board) {
int m = 2, n = 3;
StringBuilder sb = new StringBuilder();
String target = "123450";
// 将 2x3 的数组转化成字符串作为 BFS 的起点
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sb.append(board[i][j]);
}
}
String start = sb.toString();
// 记录一维字符串的相邻索引
int[][] neighbor = new int[][]{/**<extend up -200><img src="/algo/images/sliding_puzzle/4.jpeg"> */
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
/******* BFS 算法框架开始 *******/
Queue<String> q = new LinkedList<>();
HashSet<String> visited = new HashSet<>();
// 从起点开始 BFS 搜索
q.offer(start);
visited.add(start);
int step = 0;
while (!q.isEmpty()) {/**<extend up -200><img src="/algo/images/sliding_puzzle/3.jpeg"> */
int sz = q.size();
for (int i = 0; i < sz; i++) {
String cur = q.poll();
// 判断是否达到目标局面
if (target.equals(cur)) {
return step;
}
// 找到数字 0 的索引
int idx = 0;
for (; cur.charAt(idx) != '0'; idx++) ;
// 将数字 0 和相邻的数字交换位置
for (int adj : neighbor[idx]) {
String new_board = swap(cur.toCharArray(), adj, idx);
// 防止走回头路
if (!visited.contains(new_board)) {
q.offer(new_board);
visited.add(new_board);
}
}
}
step++;
}
/******* BFS 算法框架结束 *******/
return -1;
}
private String swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
return new String(chars);
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
int slidingPuzzle(vector<vector<int>>& board) {
int m = 2, n = 3;
string target = "123450";
string start = "";
// 将 2x3 的数组转化成字符串作为 BFS 的起点
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
start += to_string(board[i][j]);
}
}
// 记录一维字符串的相邻索引
vector<vector<int>> neighbor = {/**<extend up -200><img src="/algo/images/sliding_puzzle/4.jpeg"> */
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
/******* BFS 算法框架开始 *******/
queue<string> q;
unordered_set<string> visited;
// 从起点开始 BFS 搜索
q.push(start);
visited.insert(start);
int step = 0;
while (!q.empty()) {/**<extend up -200><img src="/algo/images/sliding_puzzle/3.jpeg"> */
int sz = q.size();
for (int i = 0; i < sz; i++) {
string cur = q.front();
q.pop();
// 判断是否达到目标局面
if (target == cur) {
return step;
}
// 找到数字 0 的索引
int idx = 0;
for (; cur[idx] != '0'; idx++);
// 将数字 0 和相邻的数字交换位置
for (int adj : neighbor[idx]) {
string new_board = swap(cur, adj, idx);
// 防止走回头路
if (!visited.count(new_board)) {
q.push(new_board);
visited.insert(new_board);
}
}
}
step++;
}
/******* BFS 算法框架结束 *******/
return -1;
}
string swap(string s, int i, int j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
return s;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def slidingPuzzle(board: List[List[int]]) -> int:
m, n = 2, 3
sb = []
target = "123450"
# 将 2x3 的数组转化成字符串作为 BFS 的起点
for i in range(m):
for j in range(n):
sb.append(str(board[i][j]))
start = ''.join(sb)
# 记录一维字符串的相邻索引
neighbor = [[1, 3], [0, 4, 2], [1, 5], [0, 4], [3, 1, 5], [4, 2]]
/******* BFS 算法框架开始 *******/
q = collections.deque()
visited = set()
# 从起点开始 BFS 搜索
q.append(start)
visited.add(start)
step = 0
while q:
sz = len(q)
for i in range(sz):
cur = q.popleft()
# 判断是否达到目标局面
if target == cur:
return step
# 找到数字 0 的索引
idx = cur.index('0')
# 将数字 0 和相邻的数字交换位置
for adj in neighbor[idx]:
chars = list(cur)
chars[idx], chars[adj] = chars[adj], chars[idx]
new_board = ''.join(chars)
# 防止走回头路
if new_board not in visited:
q.append(new_board)
visited.add(new_board)
step += 1
/******* BFS 算法框架结束 *******/
return -1
def swap(chars, i, j):
chars[i], chars[j] = chars[j], chars[i]
return ''.join(chars)
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func slidingPuzzle(board [][]int) int {
m, n := 2, 3
sb := strings.Builder{}
target := "123450"
// 将 2x3 的数组转化成字符串作为 BFS 的起点
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
sb.WriteString(strconv.Itoa(board[i][j]))
}
}
start := sb.String()
// 记录一维字符串的相邻索引
neighbor := [][]int{
//{1, 3},
//{0, 4, 2},
//{1, 5},
//{0, 4},
//{3, 1, 5},
//{4, 2}}
[]int{1, 3},
[]int{0, 4, 2},
[]int{1, 5},
[]int{0, 4},
[]int{3, 1, 5},
[]int{4, 2},
}
/******* BFS 算法框架开始 *******/
q := []string{start}
visited := map[string]bool{start: true}
step := 0
for len(q) > 0 {
sz := len(q)
for i := 0; i < sz; i++ {
cur := q[0]
q = q[1:]
// 判断是否达到目标局面
if target == cur {
return step
}
// 找到数字 0 的索引
idx := 0
for ; cur[idx] != '0'; idx++ {
}
// 将数字 0 和相邻的数字交换位置
for _, adj := range neighbor[idx] {
new_board := swap([]byte(cur), adj, idx)
// 防止走回头路
if _, ok := visited[new_board]; !ok {
q = append(q, new_board)
visited[new_board] = true
}
}
}
step++
}
/******* BFS 算法框架结束 *******/
return -1
}
func swap(chars []byte, i int, j int) string {
temp := chars[i]
chars[i] = chars[j]
chars[j] = temp
return string(chars)
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var slidingPuzzle = function(board) {
var m = 2, n = 3;
var sb = "";
var target = "123450";
// 将 2x3 的数组转化成字符串作为 BFS 的起点
for (var i = 0; i < m; i++) {
for (var j = 0; j < n; j++) {
sb += board[i][j].toString();
}
}
var start = sb.toString();
// 记录一维字符串的相邻索引
var neighbor = [
// extend up -200>
//<figure><img src="/images/sliding_puzzle/4.jpeg"
class="shadow myimage"/>
</figure>
[1, 3],
[0, 4, 2],
[1, 5],
[0, 4],
[3, 1, 5],
[4, 2]
];
/******* BFS 算法框架开始 *******/
var q = [];
var visited = new Set();
// 从起点开始 BFS 搜索
q.push(start);
visited.add(start);
var step = 0;
while (q.length > 0) {
// extend up -200>
//<figure><img src="/images/sliding_puzzle/3.jpeg"
class="shadow myimage"/>
</figure>
var sz = q.length;
for (var i = 0; i < sz; i++) {
var cur = q.shift();
// 判断是否达到目标局面
if (target === cur) {
return step;
}
// 找到数字 0 的索引
var idx = 0;
for (; cur.charAt(idx) !== '0'; idx++);
// 将数字 0 和相邻的数字交换位置
for (var adj of neighbor[idx]) {
var chars = cur.split('');
var new_board = swap(chars, adj, idx);
// 防止走回头路
if (!visited.has(new_board)) {
q.push(new_board);
visited.add(new_board);
}
}
}
step++;
}
/******* BFS 算法框架结束 *******/
return -1;
};
var swap = function(chars, i, j) {
var temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
return chars.join('');
}
至此，这道题目就解决了，其实框架完全没有变，套路都是一样的，我们只是花了比较多的时间将滑动拼图游戏转化成 BFS 算法。
很多益智游戏都是这样，虽然看起来特别巧妙，但都架不住暴力穷举，常用的算法就是回溯算法或者 BFS 算法。
引用本文的文章
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释