狐狸、兔子和蘑菇
导语
好久没更新，从去年十月份来，工作突然很忙，平时剩下的时间用来学习、健身，给到总结写作，没剩下时间。加上人每隔一段时间，都会产生懈怠，就停更个人技术博客近半年。想想去年因为疫情在家办公期间，某种程度上来看，还是很幸福的，上班不用来回坐车，节省下来的时间，可以花在自己感兴趣的事情上，产生一些输出。
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搜索算法，但是面对一个没有参考答案的问题，建模、优化和调试，哪一样都不轻松，很开心，今天可以完成任务，并且写下这篇文章，明天继续加油～
