C++ 迷宫问题

川长思鸟来 2024-03-16 09:42 78阅读 0赞

#### 文章目录 ####

*  题目描述
 *   *  输入描述
     *  输出描述
     *   *  示例1
 *  答案：
 *  代码讲解：

## 题目描述 ##

在一个给定大小的迷宫中，有一个起点和一个终点，中间夹杂着一些墙壁  
如果能走到终点输出 YES  
否则输出 NO

### 输入描述 ###

迷宫的大小 n×m，其中 n 表示行数，m 表示列数；  
一个由 0 和 1 组成的 n×m 的矩阵 maze，其中 0 表示通路，1 表示墙壁，起点为 maze\[0\]\[0\]，终点为 maze\[n-1\]\[m-1\]。

### 输出描述 ###

输出 YES 或 NO

#### 示例1 ####

输入

4 4
    0 1 0 0
    0 0 0 1
    0 1 0 1
    0 0 0 0

输出

YES

输入

3 3
    0 0 1
    1 1 0
    1 0 0

## 答案： ##

#include<iostream>
    using namespace std;
    int n, m, arr[1005][1005], flag = 0;
    //下，右，上。左
    const int fx[4] = {
         1,0,-1,0 }, fy[4] = {
         0,1,0,-1 };
    void search(int i, int j)
    {
        
        int nx=0, ny=0;
        //开始查询四个方向
        for (int k = 0; k < 4; k++)
        {
        
            nx = i + fx[k];
            ny = j + fy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] == 0)
            {
        
                arr[nx][ny] = 3;
                if (nx == n - 1 && ny == m - 1)
                {
        
                    arr[nx][ny] = 0;
                    flag = 1;
                }
                else
                {
        
                    search(nx, ny);
                }
            }
        }
        arr[i][j] = 0;
    }
    int main()
    {
        
        cin >> n >> m;
        for (int i = 0; i < n; i++)
        {
        
            for (int j = 0; j < m; j++)
            {
        
                cin >> arr[i][j];
            }
        }
        search(0, 0);
        if (flag == 1)
        {
        
            cout << "YES" << endl;
        }
        else
        {
        
            cout << "NO" << endl;
        }
        return 0;
    }

## 代码讲解： ##

1. 定义了一个二维数组arr，用来存储迷宫的信息，其中0表示通路，1表示墙壁。

2. 定义了一个常量数组fx和fy，用来表示四个方向的偏移量，即下，右，上，左。

3. 定义了一个递归函数search，用来从当前位置（i，j）开始搜索路径。函数的逻辑如下：

· 定义两个变量nx和ny，用来表示下一个位置的坐标。  
· 遍历四个方向，对于每个方向，计算下一个位置的坐标，并判断是否合法，即是否在迷宫范围·内，并且是否是通路。  
· 如果下一个位置是合法的，就将其标记为3，表示已经访问过，并且判断是否是终点。如果是终点，就将其标记为0，并将flag设为1，表示找到了路径。如果不是终点，就递归地调用search函数。  
· 最后将当前位置标记为0，表示回溯。

4. 在main函数中，输入迷宫的大小和信息，并调用search函数从起点开始搜索。如果flag为1，就输出YES，否则输出NO。

![在这里插入图片描述][81cca6d3d1ae4cf79eca036be0cc03f9.jpeg_pic_center]

学的不是技术，更是梦想！！！

[81cca6d3d1ae4cf79eca036be0cc03f9.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/7f4afa43212a4abca3745df7cefbcd9c.png