c++采用递归求解迷宫问题

递归求解迷宫问题是一种常见的解决方法。其基本思路是：从起点开始，依次尝试向上、向下、向左、向右四个方向移动，如果能够移动，则继续递归下去，直到到达终点或者无法继续移动为止。

具体步骤如下：

1. 定义一个二维数组表示迷宫，用0表示墙，1表示路。

2. 定义一个递归函数，接收当前坐标和目标坐标作为参数。

3. 判断当前坐标是否为终点，如果是则返回true。

4. 判断当前坐标是否越界或者是墙，如果是则返回false。

5. 尝试向上、向下、向左、向右四个方向移动，如果能够移动，则继续递归下去。

6. 如果四个方向都无法移动，则返回false。

7. 在递归返回时，将当前坐标标记为已访问，避免重复访问。

8. 在主程序中调用递归函数，判断是否能够到达终点。

下面是一个示例代码：

#include <iostream>
using namespace std;

const int N = 10;
int maze[N][N] = {
    {0,0,0,0,0,0,0,0,0,0},
    {0,1,1,1,1,0,1,1,1,0},
    {0,0,0,0,1,0,1,0,0,0},
    {0,1,1,0,1,0,1,0,1,0},
    {0,1,0,0,1,1,1,0,1,0},
    {0,1,1,1,0,0,0,1,1,0},
    {0,0,0,0,0,1,0,0,0,0},
    {0,1,1,1,0,1,1,1,1,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0}
};

bool visited[N][N] = {false};

bool dfs(int x, int y, int tx, int ty)
{
    if(x == tx && y == ty) return true; // 到达终点，返回true

    if(x < 0 || x >= N || y < 0 || y >= N || maze[x][y] == 0 || visited[x][y]) return false; // 越界或者是墙或者已经访问过，返回false

    visited[x][y] = true; // 标记已访问

    if(dfs(x-1, y, tx, ty)) return true; // 尝试向上移动

    if(dfs(x+1, y, tx, ty)) return true; // 尝试向下移动

    if(dfs(x, y-1, tx, ty)) return true; // 尝试向左移动

    if(dfs(x, y+1, tx, ty)) return true; // 尝试向右移动

    visited[x][y] = false; // 递归返回时，将当前坐标标记为未访问

    return false; // 四个方向都无法移动，返回false
}

int main()
{
    int sx = 1, sy = 1, tx = 8, ty = 8;
    if(dfs(sx, sy, tx, ty)) cout << "可以到达终点" << endl;
    else cout << "无法到达终点" << endl;
    return 0;
}