回溯算法 迷宫问题c++

回溯算法是一种经典的解决问题的算法，它的基本思想是在问题的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。当搜索到某个节点时，如果该节点不满足问题的约束条件，则回溯到该节点的父节点，继续搜索。迷宫问题是回溯算法的一个经典应用，通过回溯算法可以生成迷宫并求解迷宫。

下面是C++实现迷宫的代码：

1.初始化迷宫

vector<vector<Point>> InitMaze(vector<vector<Point>> maze, int n) {
//初始化迷宫 迷宫边缘赋0，其余处0，1间隔
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if ((i + j) % 2 == 0 && i != 0 && j != 0 && i != n - 1 && j != n - 1 && i % 2 != 0) {
maze[i][j].x = i;
maze[i][j].y = j;
maze[i][j].value = 1;
maze[i][j].flag = false; //用于判断之前是否已经到达过这个方块
}
}
}
return maze;
}

2.生成迷宫

void CreateMaze(vector<vector<Point>> &maze, int n) {
stack<Point> s;
Point cur;
cur.x = 1;
cur.y = 1;
s.push(cur);
while (!s.empty()) {
cur = s.top();
s.pop();
if (cur.x == n - 2 && cur.y == n - 2) {
break;
}
if (maze[cur.x][cur.y].flag) {
continue;
}
maze[cur.x][cur.y].flag = true;
int direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
random_shuffle(direction, direction + 4);
for (int i = 0; i < 4; i++) {
int next_x = cur.x + direction[i] * 2;
int next_y = cur.y + direction[i] * 2;
if (next_x >= 1 && next_x < n - 1 && next_y >= 1 && next_y < n - 1 && !maze[next_x][next_y].flag) {
s.push(maze[next_x][next_y]);
maze[(cur.x + next_x) / 2][(cur.y + next_y) / 2].value = 1;
}
}
}
}

3.求解迷宫

bool FindPath(vector<vector<Point>> &maze, int n, int x, int y) {
if (x == n - 2 && y == n - 2) {
maze[x][y].value = 2;
return true;
}
if (maze[x][y].value == 0 || maze[x][y].flag) {
return false;
}
maze[x][y].flag = true;
if (FindPath(maze, n, x + 1, y) || FindPath(maze, n, x - 1, y) || FindPath(maze, n, x, y + 1) || FindPath(maze, n, x, y - 1)) {
maze[x][y].value = 2;
return true;
}
return false;
}