【华为OD机试真题 C语言】机器人走迷宫_机器人走迷宫问题

题目：

1、房间由X*Y的方格组成，例如下图为6*4的大小。每一个方格以坐标(x，y)描述。
2、机器人固定从方格(0，0)出发，只能向东或者向北前进。出口固定为房间的最东角，如下图的方格(5，3)。用例保证机器人可以从入口走到出口。
3、房间有些方格是墙壁，如(4，1)，机器人不能经过那儿。
4、有些地方是一旦到达就无法走到出口的,如标记为B的方格,称之为陷阱方格。
5、有些地方是机器人无法到达的的，如标记为A的方格，称之为不可达方格，不可达方	格不包括墙壁所在的位置。
6、如下示例图中，陷阱方格有2个,不可达方格有3个。
7、请为该机器人实现路径规划功能:给定房间大小、墙壁位置，请计算出陷阱方格与不可达方格分别有多少个。
1
2
3
4
5
6
7

思路

首先，我们约定，0代表未走，1是已走，2是墙壁，3是陷阱。 当我们每走一步，就把该为赋值为1表示已经走了。

首先，分配空间。因为每行的列数都固定，都是n。所以我们写一个int i = 0专门去循环分配空间，因为空间要有多个，所以：for(int i = 0; i < m行； ++i)，grid[i]就是这个指针数组的每一个的元素。它指向的是一个int*,也就是一个一维数组。所以：grid[i] = (int *)malloc(sizeof(int)*n)，然后写memset把元素全部初始化为0。此时二维数组就分配好了。

然后我们要定义墙壁个数并输入个数(int wallCnt墙壁个数，scanf(“%d”, &wallCnt))，再循环输入墙壁的下标。我定义一个int x = 0; int y = 0; 再从控制台读进来，让grid[x][y] = 2。(2代表墙壁)

接下来递归， 递归函数是dfs。(递归函数暂不实现，先把框架搭好)

递归写完之后需要统计墙壁和陷阱个数，写一个函数函数用来统计个数。此函数是getCount()。我可以写一个函数调两次，根据传过来的type值不同，来返回不同的个数。

调用完递归函数后，最后我们需要输出陷阱和未走的个数。因为到最后的时候，没有走就是无法到达的，即陷阱是3的个数。

输出完后，我们需要free这个数组，我们得先依次free中间的每个元素的指向（for(i = 0; i < m; ++i){free(grid[i]);}），才能free整个指针数组(free(grid))。再让它指向NULL(grid = NULL)。结束！

等这个框架搭完后，就只剩下递归函数没有写了。dfs函数，把数组grid传递过去，再把行列数m，n传递过去。再把当前的位置传过去，即一开始的起点(0,0)传过去。

要传的值传过去后，我们要考虑怎么走，先判断边界值问题。

什么时候代表不可走了呢？
第一种情况：越界。(if(x >=m) || y >=n) {return 0;}
第二种情况：遇到墙。（2就是墙）(if(gird[x][y] == 2){return 0;}

然后，未走的情况要变成已走。 grid[x][y] = 1;

走到终点就不走了。
if(x == m - 1 && y == n - 1){return 1;}

剩下的就继续调用dfs函数。

此时，不可达已经解决了。
只剩下在这个递归函数里面把陷阱的情况写到位。也就是说，当向上和向右都有问题时，就证明此处是陷阱。
我们定义一个int a接收向上的结果，int b接收向右的结果。
(x+1代表往下一行走，地图虽然是往上的，但二维数组实际上是往下的。
a = dfs(grid, m, n, x + 1, y);
b = dfs(grid, m, n, x, y + 1); )

如果a,b返回的结果都为0，代表向上向右都有问题，就说明当前的位置是个陷阱，此时把这个坐标的值赋值为3.(if(a == 0 && b == 0)){grid[x][y]=3;})而且一定是它进去又回来返回的结果是3.也就是回溯。 给第二个if判断语句种加上陷阱的判断条件(grid[x][y]==3) ，此题结束。

代码

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

int getCount(int ** grid, int m, int n, int type){
    int i = 0; //统计 0 或者 3的个数
    int j = 0;
    int cnt = 0;
    for(i = 0; i < m; ++i){
        for(j = 0; j < n; ++j){
            if(grid[i][j] == type){
                cnt++;
            }
        }
    }
    return cnt;
}

int dfs(int ** grid, int m, int n, int x, int y){
    int a = 0;
    int b = 0;
    if(x >= m || y >= n){ //越界
        return 0;
    }
    if(grid[x][y] == 2 || grid[x][y] == 3){
        return 0; //遇到墙壁或陷阱
    }
    grid[x][y] = 1; //不是墙壁 也不是陷阱 就改为1
    
    if(x == m - 1 && y == n - 1){ //走到终点
        return 1;  
    }
    a = dfs(grid, m, n, x + 1, y);
    b = dfs(grid, m, n, x, y + 1);
    if(a == 0 && b == 0){ //当两条路都返回为假 则代表当前为陷阱
        grid[x][y] = 3;
    }
    return grid[x][y] != 3; //往上一级返回一个信号0
}

int main(){
    int m = 0;
    int n = 0;
    int i = 0;
    int ACnt = 0; //不可达   
    int BCnt = 0; //陷阱
    int wallCnt = 0;
    int ** grid = NULL;
    scanf("%d%d", &m, &n);
    grid = (int **)malloc(sizeof(int *) * m);
    memset(grid, 0, sizeof(int *) * m);
    for(i = 0; i < m; ++i){
        grid[i] = (int *)malloc(sizeof(int) * n);
        memset(grid[i], 0, sizeof(int) * n);
    }
    scanf("%d", &wallCnt);
    for(i = 0; i < wallCnt; ++i){
        int x = 0;
        int y = 0;
        scanf("%d%d", &x, &y);
        grid[x][y] = 2; //2 就是墙壁
    }
    dfs(grid, m, n, 0, 0);
    printf("%d %d\n", getCount(grid, m, n, 0), getCount(grid, m, n, 3));
    for(i = 0; i < m; ++i){
        free(grid[i]);
    }
    free(grid);
    grid = NULL;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72