🧠 回溯算法步骤
1. 从起点开始探索
2. 标记当前位置为已访问
3. 尝试四个方向：上下左右
4. 如果找到有效路径，继续递归
5. 如果所有方向都无效，回溯
6. 取消当前位置标记，返回上一步
0
探索步数
0
回溯次数
0
访问格子
0s
探险时间
📊 变量状态监控
x = - (当前行)
y = - (当前列)
depth = 0 (递归深度)
direction = - (当前方向)
visited[x][y] = false (访问状态)
isValid = - (位置有效性)
💻 C++ 回溯算法实现
// 魔法迷宫寻宝 - 回溯算法实现
#include <iostream>
#include <vector>
using namespace std;
class MazeExplorer {
private:
vector<vector<int>> maze;
vector<vector<bool>> visited;
int rows, cols;
int dx[4] = {-1, 0, 1, 0}; // 上右下左
int dy[4] = {0, 1, 0, -1};
public:
MazeExplorer(int r, int c) : rows(r), cols(c) {
maze.resize(rows, vector<int>(cols));
visited.resize(rows, vector<bool>(cols, false));
}
// 检查位置是否有效
bool isValid(int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols &&
maze[x][y] != 1 && !visited[x][y];
}
// 回溯搜索主函数
bool backtrack(int x, int y, int targetX, int targetY) {
// 到达目标位置
if (x == targetX && y == targetY) {
cout << "找到宝藏了！位置: (" << x << ", " << y << ")" << endl;
return true;
}
// 标记当前位置为已访问
visited[x][y] = true;
cout << "探索位置: (" << x << ", " << y << ")" << endl;
// 尝试四个方向
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
// 如果新位置有效，递归探索
if (isValid(newX, newY)) {
if (backtrack(newX, newY, targetX, targetY)) {
return true; // 找到路径
}
}
}
// 回溯：取消标记
visited[x][y] = false;
cout << "回溯从位置: (" << x << ", " << y << ")" << endl;
return false;
}
};