关于算法:如何用-BFS-算法秒杀各种智力题

7次阅读

共计 2195 个字符，预计需要花费 6 分钟才能阅读完成。

读完本文，你能够去力扣拿下如下题目：

773. 滑动谜题

———–

滑动拼图游戏大家应该都玩过，下图是一个 4×4 的滑动拼图：

拼图中有一个格子是空的，能够利用这个空着的格子挪动其余数字。你须要通过挪动这些数字，失去某个特定排列程序，这样就算赢了。

我小时候还玩过一款叫做「华容道」的益智游戏，也和滑动拼图比拟相似。

那么这种游戏怎么玩呢？我记得是有一些套路的，相似于魔方还原公式。然而咱们明天不来钻研让人头秃的技巧， 这些益智游戏统统能够用暴力搜索算法解决，所以明天咱们就学以致用，用 BFS 算法框架来秒杀这些游戏 。

LeetCode 第 773 题就是滑动拼图问题，题目的意思如下：

给你一个 2×3 的滑动拼图，用一个 2×3 的数组 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,0,4]]，则算法返回 -1，因为这种场面下无论如何都不能博得游戏。

对于这种计算最小步数的问题，咱们就要敏感地想到 BFS 算法。

这个题目转化成 BFS 问题是有一些技巧的，咱们面临如下问题：

1、个别的 BFS 算法，是从一个终点 start 开始，向起点 target 进行寻路，然而拼图问题不是在寻路，而是在一直替换数字，这应该怎么转化成 BFS 算法问题呢？

2、即使这个问题可能转化成 BFS 问题，如何解决终点 start 和起点 target？它们都是数组哎，把数组放进队列，套 BFS 框架，想想就比拟麻烦且低效。

首先答复第一个问题，BFS 算法并不只是一个寻路算法，而是一种暴力搜索算法 ，只有波及暴力穷举的问题，BFS 就能够用，而且能够最快地找到答案。

你想想计算机怎么解决问题的？哪有那么多奇技淫巧，实质上就是把所有可行解暴力穷举进去，而后从中找到一个最优解罢了。

明确了这个情理，咱们的问题就转化成了： 如何穷举出 board 以后场面下可能衍生出的所有场面 ？这就简略了，看数字 0 的地位呗，和上下左右的数字进行替换就行了：

这样其实就是一个 BFS 问题，每次先找到数字 0，而后和四周的数字进行替换，造成新的场面退出队列…… 当第一次达到 target 时，就失去了博得游戏的起码步数。

对于第二个问题，咱们这里的 board 仅仅是 2×3 的二维数组，所以能够压缩成一个一维字符串。 其中比拟有技巧性的点在于，二维数组有「上下左右」的概念，压缩成一维后，如何失去某一个索引上下左右的索引 ？

很简略，咱们只有手动写进去这个映射就行了：

vector<vector<int>> neighbor = {{ 1, 3},
    {0, 4, 2},
    {1, 5},
    {0, 4},
    {3, 1, 5},
    {4, 2}
};

这个含意就是，在一维字符串中，索引 i 在二维数组中的的相邻索引为 neighbor[i]，：

至此，咱们就把这个问题齐全转化成规范的 BFS 问题了，借助前文 BFS 算法框架的代码框架，间接就能够套出解法代码了：

int slidingPuzzle(vector<vector<int>>& board) {
    int m = 2, n = 3;
    string start = "";
    string target = "123450";
    // 将 2x3 的数组转化成字符串
    for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {start.push_back(board[i][j] + '0');
        }
    }
    // 记录一维字符串的相邻索引
    vector<vector<int>> neighbor = {{ 1, 3},
        {0, 4, 2},
        {1, 5},
        {0, 4},
        {3, 1, 5},
        {4, 2}
    };
    
    /******* BFS 算法框架开始 *******/
    queue<string> q;
    unordered_set<string> visited;
    q.push(start);
    visited.insert(start);
    
    int step = 0;
    while (!q.empty()) {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 = cur;
                swap(new_board[adj], new_board[idx]);
                // 避免走回头路
                if (!visited.count(new_board)) {q.push(new_board);
                    visited.insert(new_board);
                }
            }
        }
        step++;
    }
    return -1;
    /******* BFS 算法框架完结 *******/
}

至此，这道题目就解决了，其实框架齐全没有变，套路都是一样的，咱们只是花了比拟多的工夫将滑动拼图游戏转化成 BFS 算法。

很多益智游戏都是这样，尽管看起来特地奇妙，但都架不住暴力穷举，罕用的算法就是回溯算法或者 BFS 算法。

正文完