用DFS解决最终幻想13-2时钟谜题
最近在补 XGP 中的最终幻想13-2时,遇到一个时钟谜题,感觉挺有意思,就像尝试用搜索算法将其解决。
问题描述
如下图所示,有一个时钟,包含个结点,每个节点有一个数字标识,玩家最开始可以任意选择一个结点,选择后,该结点被消除且指针会指向该结点的位置,根据该节点的数字值 n 分裂为两根指针分别向顺时针方向和逆时针方向旋转 n 个的单位长度。此后每次玩家只能选择指针指向的结点,选择结点后结点被消除,两指针合并指向选择结点的位置并按上述描述进行分裂和旋转,玩家需要将所有节点消除才能胜利。
注:玩家无法选择已经被消除的结点,若分裂旋转后的两指针均位于已被消除的结点位置,则判定游戏失败。
算法思路
本问题很容易想到利用深度优先搜索来解决,选择一个结点作为开始,如第一次选择 12 点钟位置的结点,(以下为了方便,按结点在时钟中排布位置 n 称作结点 n)该结点值为 5,则选中后分别向顺时针和逆时针方向旋转到达结点 5 和 结点 7,这就产生了两个分支(相当于二叉树的左右子树),分别选择这两个结点继续搜索,若结点到达了一个已被访问过的结点(即该结点已被消除),则终止该方向上的搜索,并进行回溯,将路径上的该结点删除,并将访问标志复原。
若路径上的结点个数已经达到 12,即所有节点均被成功消除,则该路径为一个解路径,将该结果保存并回溯继续进行搜索,直到尝试了所有可能性,算法结束。
完整代码
#include<iostream>
#include<vector>
using namespace std;
class Solution {
private:
int n;
vector<int> path; // 搜索路径
vector<vector<int>> res; // 成功路径
void dfs(vector<int>& sequences, vector<bool>& visited, int ind) {
if (visited[ind]) { // 已访问过
return;
}
path.emplace_back(ind);
visited[ind] = true;
if (path.size() == n) { // 成功访问所有元素
res.emplace_back(path);
}
int p1 = (ind - sequences[ind] + n) % n; // 逆时针方向旋转后的下标
int p2 = (ind + sequences[ind]) % n; // 顺时针方向旋转后的下标
if (p1 == p2) {
dfs(sequences, visited, p1);
}
else {
dfs(sequences, visited, p1);
dfs(sequences, visited, p2);
}
// 回溯
path.pop_back();
visited[ind] = false;
}
public:
vector<vector<int>> clockPuzzle(vector<int>& sequences) {
n = sequences.size();
vector<bool> visited;
for (int i = 0; i < n; ++i) { // 选取一个结点作为开始结点
visited.assign(n, false); // 重置visited数组
dfs(sequences, visited, i);
}
return res;
}
};
int main() {
Solution S;
vector<int> sequences = { 5,5,3,6,2,1,4,3,4,5,3,4 };
auto res = S.clockPuzzle(sequences);
for (const auto& re : res) {
for (const auto& r : re) {
cout << r << " ";
}
cout << endl << endl;
}
}
结果分析
以下为示例图中问题的所有解路径,经验证,符合条件。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Lordaeron_ESZ's blog!
评论