26. 机器人走迷宫

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.房间由X*Y的方格组成，每一个方格以（x，y）描述

2.机器人固定从方格（0，0）出发，只能向东或者向北前进。

3.出口固定为房间的最东角，（x-1，y-1）

4.用例保证机器人可以从入口走到出口

5.有些方格是墙壁，机器人不能经过

6.有些地方是一旦到达就无法走到出口的，如标记为B的方格，称之为陷阱方格

7.有些地方是机器人无法到达的，如标记为A的方格，称之为不可达方格，不可达方格不包括墙壁所在的位置。

8.为该机器人实现路径规划功能：给定房间大小、墙壁位置，请计算出陷阱方格与不可达方格分别有多少个。

9.输入描述：第一行为房间的X和Y，X，Y大于0小于等于1000

第二行为房间中墙壁的个数N（N大于等于0小于X*Y）

接着下面会有N行墙壁的坐标

同一行中如果有多个数据以一个空格隔开，用例保证所有的输入数据均合法（结尾不带回车换行）

10.输出描述：陷阱方格与不可达方格数量，两个信息在一行中输出，以一个空格隔开。（结尾不带回车换行）

二、解题思路

1.首先我们定义一个结构体Maze，其中包括

typedef struct {

        int **map; 一个二维数组map用来表示迷宫地图，如果0表示可以通过，1表示墙壁，2表示已访问，3表示陷阱（无法到达终点）

        int height; 表示迷宫高度

        int width;表示迷宫宽度

        int trapCount;表示陷阱数量

        int unreachableCount;表示不可达方格数量（需要最后才能知道）

        bool reachend;

} Maze;

2.然后我们需要一个函数用于初始化迷宫需要的参数有width和height

Maze* createMaze(int height, int width) {

Maze *maze = (Maze *)malloc(sizeof(Maze)); //首先分配内存

maze->height = height;

maze->width = width;

maze->trapCount = 0;

maze->unreachableCount = 0;

还需要为map分配内存

maze->map = (int **)malloc(sizeof(int *) * height);

for(int i = 0; i < height; i++) {

maze->map[i] = (int *)malloc(sizeof(int) * width);

for(int j = 0; j < width; j++) {

maze->map[i][j] = 0;

}

maze->reachend = false;

}

最后返回我们初始化好的maze

return maze;

}

3.因为我们为maze迷宫结构体分配了内存，我们需要一个释放内存的函数

void freeMaze(Maze *maze) {

for(int i = 0; i < maze->height; i++) {

free(maze->map[i]);

}

free(maze->map);

free(maze);

}

4.在遍历图像的过程中我们使用深度优先搜索的方式（dfs），我们在遍历的过程中

我们需要判断某个坐标是否可以通过如果不可以通过我们就不能访问这个坐标

int isValid(Maze *maze, int x, int y) {

return x >= 0 && x < maze->width && y >= 0 && y < maze->height && maze->map[y][x] != 1;

}

如果超过了地图范围或者是墙壁的情况下我们返回-1，（因为我们先给高度分配的内存然后给宽度分配的内存，所以我们坐标是y，x）

5.之后我们还需要一个深度优先搜索的函数，dfs，函数需要的参数有地图maze，以及坐标下，

y

void dfs(Maze *maze, int x, int y) {

在dfs函数中我们先判断如果坐标是无效的情况下或者已经访问过了的话我们不重复访问，（因为如果之前已经对这个坐标使用过dfs函数了，没有必要再重复一次）

if(!isValid(maze, x, y) || maze->map[y][x] == 2) return;因为我们采取标记地图的方式所以不需要返回任何数据

如果程序可以继续进行证明这是一个没有访问过的且有效的坐标

我们先判断一下是否到达了终点，如果到达终点我们将终点标记为已经访问过，然后返回

将reachend设置为true（可以到达终点的我们不设置成陷阱）

if(x == maze->width - 1 && y == maze->height - 1) {

maze->map[y][x] = 2;

maze->reachend = true;

return;

}

如果程序进行到这里证明我们访问了一个不是终点的并且有效的坐标，我们有可能在去往终点的路上，或者我们有可能进入了陷阱（但是不可能是不可达的因为我们已经到达了）

所以我们标记当前方格为已访问

maze->map[y][x] = 2;

然后我们从这个方格调用dfs函数，向右走、向上走，如果找到无效方格或者找到已经访问过的方格我们会返回，如果找到终点我们会返回，如果找到的方格是有效的，并且没有访问过，而且也不是终点，但是没有返回，证明从这个方格无法到达终点，那么我们将这个方格标记为3，陷阱方格

dfs(maze, x, y + 1);

dfs(maze ,x + 1, y);

// 如果没有没有返回我们认为不可以到达终点，那么我们标记为陷阱

if(!(maze->reachend) && (maze->map[y][x] == 2)) {

maze->map[y][x] = 3;

maze->trapCount++;

}

}

6.我们还需要一个函数用来计算不可达的方格数量（整个迷宫使用dfs遍历过之后还没有被标记为1墙壁、2已访问、3陷阱）的方格也就是说还是0的方格是不可达方格

void countUnreachable(Maze *maze) {

for(int i = 0; i < maze->height; i++){

for(int j = 0; j < maze->width; j++) {

if(maze->map[i][j] == 0) {

maze->unreachableCount++;

}

}

}

}

7.然后是主函数

int main() {

我们首先定义变量读取输入中的数据

int width, height;

scanf("%d %d", &width, &height);

然后初始化迷宫

Maze *maze = createMaze(width, height);

读取墙壁并在迷宫map上标记

首先读取墙壁数目

int wallCount;

scanf("%d", &wallCount);

for(int i = 0; i < wallCount; i++) {

int x, y;

scanf("%d %d", &x, &y);

maze->map[y][x] = 1;

}

然后我们从原点开始进行深度优先搜索

dfs(maze, 0 , 0);

然后我们计算不可达方格数量

countUnreachable(maze);

然后我们输出陷阱和不可达方格的数量

printf("%d %d\n", maze->trapCount, maze->unreachableCount);

最后别忘了释放内存

freeMaze(maze);

return 0;

}

三、具体步骤

使用的语言是C

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int width;
    int height;
    int** map;
    int trapCount;
    int unreachableCount;
    bool reachEnd;
} Maze;

Maze* createMaze(int width, int height) {
    Maze* maze = (Maze*)malloc(sizeof(Maze));
    maze->width = width;
    maze->height = height;
    maze->trapCount = 0;
    maze->unreachableCount = 0;
    maze->map = (int**)malloc(height * sizeof(int*));
    for (int i = 0; i < height; i++) {
        maze->map[i] = (int*)malloc(width * sizeof(int));
        for (int j = 0; j < width; j++) {
            maze->map[i][j] = 0; // 0表示还没有访问过
        }
    }
    maze->reachEnd = false;
    return maze;
}

void freeMaze(Maze* maze) {
    for (int i = 0; i < maze->height; i++) {
        free(maze->map[i]);
    }
    free(maze->map);
    free(maze);
}

void printMaze(Maze* maze) {
    for (int i = maze->height - 1; i >= 0; i--) {
        for (int j = 0; j < maze->width; j++) {
            printf("%d ", maze->map[i][j]);
        }
        printf("\n");
    }
}

bool isValid(Maze* maze, int x, int y) {
    if (x < 0 || y < 0 || x >= maze->width || y >= maze->height ||
            maze->map[y][x] == 1) {
        return false;
    }
    return true;
}

void dfs(Maze* maze, int x, int y) {
    // printf("x is %d y is %d end is %d , %d\n", y, x, maze->height - 1, maze->width - 1);
    if (!isValid(maze, x, y) || maze->map[y][x] == 2) return;
    
    if (y == maze->height - 1 && x == maze->width - 1) {
        // printf("reach end\n");
        maze->map[y][x] = 2;
        maze->reachEnd = true;
        return;
    }
    if (maze->map[y][x] == 0) {
        maze->map[y][x] = 2;
    }

    dfs(maze, x + 1, y);
    dfs(maze, x, y + 1);
    // 如果没有到达终点，并且已经访问过了
    if (!(maze->reachEnd) && (maze->map[y][x] == 2)) {
        maze->map[y][x] = 3; // 3表示是陷阱
        maze->trapCount++;
    }
    // printMaze(maze);
    // printf("\n");
}

void countUnreachable(Maze* maze) {
    for (int i = 0; i < maze->height; i++) {
        for (int j = 0; j < maze->width; j++) {
            if (maze->map[i][j] == 0) maze->unreachableCount++;
        }
    }
}



int main() {
    int width, height;
    scanf("%d %d", &width, &height);
    Maze* maze = createMaze(width, height);
    int wallCount;
    scanf("%d", &wallCount);
    for (int i = 0; i < wallCount; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        maze->map[y][x] = 1;
        // 1表示墙壁，因为我们先设置的高度然后设置的宽度，所以是y，x
    }
    // maze->map[0][0] = 5;
    // maze->map[maze->height - 1][maze->width - 1] = 6;
    // printMaze(maze);
    dfs(maze, 0, 0);
    countUnreachable(maze);
    printf("%d %d\n", maze->trapCount, maze->unreachableCount);
    // printMaze(maze);
    free(maze);
    return 0;
}