狐狸、兔子和蘑菇

导语

好久没更新，从去年十月份来，工作突然很忙，平时剩下的时间用来学习、健身，给到总结写作，没剩下时间。加上人每隔一段时间，都会产生懈怠，就停更个人技术博客近半年。想想去年因为疫情在家办公期间，某种程度上来看，还是很幸福的，上班不用来回坐车，节省下来的时间，可以花在自己感兴趣的事情上，产生一些输出。

OK，言归正传，今天闲来无事，我翻出了女儿去年玩过的小游戏，她妈妈给她买的这类智力小游戏有不少，很偶尔会瞧见她们娘俩一起玩，估计是不太感兴趣。今天这款游戏，我小时候没见过，是一个新的小游戏，我就起一个应景的名字，《兔兔大战小狐狸》，今年是兔年，兔子要逃脱小狐狸的围追堵截，逃到安全的小土坑里，躲起来。

游戏介绍

游戏棋盘是一个5*5的方盘，左上、右上、左下、右下以及正中间有5个小土坑，如果棋盘上所有的兔子，都在土坑待着，就完成了任务。具体规则，我不码字，看如下说明：

如上面所说，游戏内置了60个关卡（因为随便摆放，是不一定能完成任务的），也有最少步骤的解答，我自己尝试玩了几个简单关卡（最少10步以内可以完成的），貌似还挺简单的。

然后，我翻到了关卡的最后4个关卡，哇，一下子震惊了，好难，最后一关官方解答，需要87步完成任务。

一些疑问

小朋友如果自己完成前面简单、中等题目，已经很不容易了。至于困难、专家级别的题目，如果能完成，小脑瓜不是一般聪明，非常了不起。但我想了下，官方说最后一题87步是最少步骤，这个怎么证明官方没错呢？或者有更少步骤的解法？我心想，是不是写个算法求解，看看是否是对的。

求解过程

首先是需要有个建模过程，棋盘规格是5*5方盘，上面有25个位置，5个位置是土坑。可以放置的角色是小狐狸、兔兔和蘑菇。兔兔和蘑菇都只占用一个格子，狐狸占用两个格子，还有头和尾巴，但我仔细想了下，狐狸头和尾巴，其实在算法中不需要区分，只需要区分狐狸是竖着还是横着放置的，你可以理解为狐狸的头总是在左边或者上方，尾巴在右边或者下方。这样对算法实现更简单。

比如60题，我会使用5个字符串表示5行，

"...X."
"FF.R."
"..X.R"
"X...."
"...R."

字符X表示蘑菇，F表示小狐狸（头或者尾），R表示小兔兔，最后.表示空位。

算法显然就是搜索算法，DFS还是BFS呢？我先用DFS实现了半天，会TLE，根本算不出最少步骤的解法。我后来想了下，最少步骤的解法确实不太适合DFS，因为DFS可能需要搜索完所有的解法空间（也可能我剪枝还不够），所以无法算出最少步骤。在DFS上，我其实花了不少时间优化，这个题目比刷题难，因为是自己出给自己的，也没有什么参考答案，都只能自己去想，如何建模和实现搜索算法，总之，自己试了半天，也不work。

OK，那么我就来试下BFS搜索，大概的逻辑步骤如下：

1. 建立一个队列，将游戏初始棋盘局面放到队列中；
2. 一一取出当前局面，评估可能变为的下一个局面；
3. 评估当前局面可能可以行动的小兔兔、小狐狸坐标；
4. 一一取出小兔兔、小狐狸，评估她们可能的移动到的位置；
5. 通过改变小兔兔、小狐狸位置，得到下一个局面；
6. 将2～5变化的到的局面插入队列（下一轮）；
7. 遍历完上一轮队列，步骤+1；
8. 把下一轮队列变为需要遍历的当前队列，重复2～7步骤；

代码实现：

int smartGame(vector<string> board) {
    int n = board.size();

    // 判断游戏是否结束
    set<vector<int>> finish_pos = {{0, 0}, {0, n-1}, {n-1, 0}, {n-1, n-1}, {n/2, n/2}};
    function<bool(vector<vector<int>>)> isFinished = [&](vector<vector<int>> ani_pos) -> bool {
        int n = ani_pos.size();

        for (int i = 0; i < n; ++i) {
            if (ani_pos[i][2] != -1) continue;
            vector<int> pos = {ani_pos[i][0], ani_pos[i][1]};
            if (finish_pos.find(pos) == finish_pos.end())
                return false;
        }

        return true;
    };

    // 分析棋盘局面，哪些可能移动的小兔兔、小狐狸所在位置
    function<void(vector<string>, vector<vector<int>>&)> analyzeBoard = [&](vector<string> board, vector<vector<int>>& ani_pos) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'X') {
                    continue;
                } else if (board[i][j] == '.') {
                    continue;
                } else if (board[i][j] == 'F') {
                    if ((i == 0 || board[i - 1][j] != 'F') && (i < n - 1 && board[i + 1][j] == 'F')) {
                        // vertical fox
                        ani_pos.push_back({i, j, 1});
                    } else if ((j == 0 || board[i][j - 1] != 'F') && (j < n - 1 && board[i][j + 1] == 'F')) {
                        // horizontal fox
                        ani_pos.push_back({i, j, 2});
                    }
                } else if (board[i][j] == 'R') {
                    ani_pos.push_back({i, j, -1});
                }
            }
        }
    };

    // 棋盘局面上某个小兔兔、小狐狸，做出某个移动后，返回新的局面
    function<vector<string>(vector<string>, vector<int>, vector<int>)> applyBoard = [&] (vector<string> board, vector<int> pos, vector<int> move) -> vector<string> {
        if (pos[2] == -1) {
            board[pos[0]][pos[1]] = '.';
            board[pos[0]+move[0]][pos[1]+move[1]] = 'R';
        } else {
            if (pos[2] == 1) {
                board[pos[0]][pos[1]] = '.';
                board[pos[0]+1][pos[1]] = '.';

                board[pos[0]+move[0]][pos[1]+move[1]] = 'F';
                board[pos[0]+move[0]+1][pos[1]+move[1]] = 'F';
            } else if (pos[2] == 2) {
                board[pos[0]][pos[1]] = '.';
                board[pos[0]][pos[1]+1] = '.';

                board[pos[0]+move[0]][pos[1]+move[1]] = 'F';
                board[pos[0]+move[0]][pos[1]+move[1]+1] = 'F';
            }
        }

        return board;
    };

    // 分析棋盘局面，可能移动的小兔兔、小狐狸，能做出哪些移动
    function<vector<vector<int>>(vector<string>, vector<int>)> nextMoves = [&] (vector<string> board, vector<int> pos) -> vector<vector<int>> {
        vector<vector<int>> moves;

        if (pos[2] == -1) {
            // up
            vector<int> t = pos;
            while (t[0] >= 0 && board[t[0]][t[1]] != '.') t[0] -= 1;
            if (t[0] >= 0 && board[t[0]][t[1]] == '.' && t[0] < pos[0]-1) {
                moves.push_back({t[0]-pos[0], 0});
            }
            // down
            t = pos;
            while (t[0] < n && board[t[0]][t[1]] != '.') t[0] += 1;
            if (t[0] < n && board[t[0]][t[1]] == '.' && t[0] > pos[0]+1) {
                moves.push_back({t[0]-pos[0],0});
            }
            // left
            t = pos;
            while (t[1] >= 0 && board[t[0]][t[1]] != '.') t[1] -= 1;
            if (t[1] >= 0 && board[t[0]][t[1]] == '.' && t[1] < pos[1]-1) {
                moves.push_back({0, t[1]-pos[1]});
            }
            // right
            t = pos;
            while (t[1] < n && board[t[0]][t[1]] != '.') t[1] += 1;
            if (t[1] < n && board[t[0]][t[1]] == '.' && t[1] > pos[1]+1) {
                moves.push_back({0, t[1]-pos[1]});
            }
        } else if (pos.size() == 3) {
            if (pos[2] == 1) {
                // up
                if (pos[0] > 0 && board[pos[0]-1][pos[1]] == '.') {
                    moves.push_back({-1, 0});
                }
                // down
                if (pos[0] < n-2 && board[pos[0]+2][pos[1]] == '.') {
                    moves.push_back({1, 0});
                }
            } else if (pos[2] == 2) {
                // left
                if (pos[1] > 0 && board[pos[0]][pos[1]-1] == '.') {
                    moves.push_back({0, -1});
                }
                // right
                if (pos[1] < n-2 && board[pos[0]][pos[1]+2] == '.') {
                    moves.push_back({0, 1});
                }
            }
        }

        return moves;
    };

    // 棋盘局面的签名，用作去重
    function<string(vector<string>)> signature = [&](vector<string> board) -> string {
        string r;
        for (auto l : board) {
            r += l;
        }
        return r;
    };

    // 1. 初始棋盘局面，入到队列
    queue<vector<string>> q;
    unordered_set<string> seen;
    q.push(board);
    seen.insert(signature(board));

    int ans = 0;

    while (!q.empty()) {
        int size = q.size();
        while (size --) {
            // 2. 一一取出当前局面，评估可能变为的下一个局面；
            vector<string> t = q.front();
            q.pop();
            vector<vector<int>> ani_pos;

            // 3. 评估当前局面可能可以行动的小兔兔、小狐狸坐标；
            analyzeBoard(t, ani_pos);

            if (isFinished(ani_pos)) {
                return ans;
            }

            // 4. 一一取出小兔兔、小狐狸，评估她们可能的移动到的位置；
            for (auto pos: ani_pos) {
                vector<vector<int>> moves = nextMoves(t, pos);
                for (int i = 0; i < moves.size(); ++i) {
                    vector<int> move = moves[i];
                    // 5. 通过改变小兔兔、小狐狸位置，得到下一个局面；
                    vector<string> nxtBoard = applyBoard(t, pos, move);
                    string sig = signature(nxtBoard);
                    if (seen.find(sig) == seen.end()) {
                        // 6. 将2～5变化的到的局面插入队列（下一轮）；
                        q.push(nxtBoard);
                        seen.insert(sig);
                    }
                }
            }
        }

        // 7. 遍历完上一轮队列，步骤+1；
        // 8. 把下一轮队列变为需要遍历的当前队列，重复2～7步骤；
        ans++;
    }

    return -1;
}

还要强调一点优化，我用了一个unordered_set去做棋盘局面去重，曾经看见过的局面，就不需要再去考虑了，因为即使从该局面出发有解，肯定也不会比之前出现时更优的，这个很好理解吧。

结论

最终通过算法验证，最后4题的最优解确实和官方的步骤数量一样，并且我后来记录了最优解算法的到的步骤，虽然有些顺序和官方题解不一致，我仔细比对了下，仅仅是某些步骤中，可以交换顺序而已，不是计算错误。别看是思路很简单，就是BFS搜索算法，但是面对一个没有参考答案的问题，建模、优化和调试，哪一样都不轻松，很开心，今天可以完成任务，并且写下这篇文章，明天继续加油～