迷宫可达

比眉伴天荒 2021-09-11 02:10 344阅读 0赞

## 问题描述 ##

给定一张迷宫地图，该地图标识了迷宫各处的位置坐标，并已知迷宫个位置的状态信息，即该处是路还是墙，移动方向是东、南、西、北四个方向，判断从入口是否可以到达出口

#include <iostream>
    
    using namespace std;
    
    typedef struct Node { 
        int x;
        int y;
    } Node;
    
    /** * 创建 m 行 n 列的二维数组 * @param m 数组行数 * @param n 数组列数 * @return 数组地址 */
    int **createTwoDimensionalArray(int m, int n) { 
        int **array = (int **) malloc(sizeof(int *) * m);
        for (int i = 0; i < m; ++i) { 
            array[i] = (int *) malloc(sizeof(int) * n);
        }
        for (int i = 0; i < m; ++i) { 
            for (int j = 0; j < n; j++) { 
                array[i][j] = 0;
            }
        }
        return array;
    }
    
    /** * 给定一张 m*n 的地图，其中 0 代表墙，其余代表路，判断是否能从起始位置start 到达出口 end * @param map 地图 * @param start 起始位置 * @param endPosition 结束位置 * @param m 地图行数 * @param n 地图列数 * @return 是否能到到 */
    bool canYouArrive(int **map, Node start, Node endPosition, int m, int n) { 
        // 定义四个方向
        int next[4][2] = { 
                // 向右走
                { 0,  1},
                // 向左走
                { 0,  -1},
                // 向上走
                { 1,  0},
                // 向下走
                { -1, 0}
        };
        // 标记数组
        int **mark = createTwoDimensionalArray(m + 1, n + 1);
        // 遍历队列
        Node *traverseQueue = (Node *) malloc(sizeof(Node) * (m * n + 1));
        // 初始化队列两个游标
        int head = 1;
        int tail = 1;
        // 将降落的起始坐标插入队列
        traverseQueue[tail++] = start;
        // 将降落点标记为已遍历
        mark[start.x][start.y] = 1;
        bool flag = false;
        while (head < tail) { 
            if (flag) break;
            // 枚举当前点的四个方向
            for (int i = 0; i < 4; i++) { 
                // 下一个的坐标
                int x = traverseQueue[head].x + next[i][0];
                int y = traverseQueue[head].y + next[i][1];
                // 判断是否越界
                if (x < 1 || x > m || y < 1 || y > n) { 
                    continue;
                }
                // 判断是否遍历过该点并且改点是否是陆地
                if (map[x][y] != 0 && mark[x][y] == 0) { 
                    // 判断该点是否是出口
                    if (x == endPosition.x && y == endPosition.y) { 
                        flag = true;
                        break;
                    }
                    // 入队该节点并标记为已遍历
                    Node temp;
                    temp.x = x;
                    temp.y = y;
                    traverseQueue[tail++] = temp;
                    mark[x][y] = 1;
                }
            }
            head++;
        }
        return flag;
    }
    
    int main() { 
        // 定义四个方向
        int next[4][2] = { 
                // 向右走
                { 0,  1},
                // 向左走
                { 0,  -1},
                // 向上走
                { 1,  0},
                // 向下走
                { -1, 0}
        };
        // 地图大小，m 行 n 列
        int m, n;
        // 输入地图大小
        cout << "输入地图大小:";
        cin >> m >> n;
        // 起始位置
        int startX, startY;
        // 输入起始位置
        cout << "起始位置:";
        cin >> startX >> startY;
        Node start;
        start.x = startX;
        start.y = startY;
        // 结束位置
        int endX, endY;
        cout << "结束位置:";
        cin >> endX >> endY;
        Node endPosition;
        endPosition.x = endX;
        endPosition.y = endY;
    
        // 加载地图
        // ① m 行 n 列的数组
        int **map = createTwoDimensionalArray(m + 1, n + 1);
        // ② 创建地图
        int num;
        for (int i = 1; i <= m; i++) { 
            for (int j = 1; j <= n; j++) { 
                cin >> num;
                map[i][j] = num;
            }
        }
    
        bool flag = canYouArrive(map, start, endPosition, m, n);
        if (flag)cout << "true" << endl;
        else cout << "false" << endl;
        return 0;
    }

## 测试数据 ##

输入地图大小:10 10
    起始位置:6 8
    结束位置:4 6
    1 2 1 0 0 0 0 0 2 3
    3 0 2 0 1 2 1 0 1 2
    4 0 1 0 1 2 3 2 0 1
    3 2 0 0 0 1 2 4 0 0
    0 0 0 0 0 0 1 5 3 0
    0 1 2 1 0 1 5 4 3 0
    0 1 2 3 1 3 6 2 1 0
    0 0 3 4 8 9 7 5 0 0
    0 0 0 3 7 8 6 0 1 2
    0 0 0 0 0 0 0 0 1 0

## 测试结果 ##

输入地图大小:10 10
    起始位置:6 8
    结束位置:4 6
    1 2 1 0 0 0 0 0 2 3
    3 0 2 0 1 2 1 0 1 2
    4 0 1 0 1 2 3 2 0 1
    3 2 0 0 0 1 2 4 0 0
    0 0 0 0 0 0 1 5 3 0
    0 1 2 1 0 1 5 4 3 0
    0 1 2 3 1 3 6 2 1 0
    0 0 3 4 8 9 7 5 0 0
    0 0 0 3 7 8 6 0 1 2
    0 0 0 0 0 0 0 0 1 0
    true

![测试图片][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDY2NDY2_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDY2NDY2_size_16_color_FFFFFF_t_70]: /images/20210911/20880151232548db89d7aa388c85ba4c.png