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

1、房间由XY的方格组成，例如下图为64的大小。每一个方格以坐标(x，y)描述。
2、机器人固定从方格(0，0)出发，只能向东或者向北前进。出口固定为房间的最东角，如下图的方格(5，3)。用例保证机器人可以从入口走到出口。
3、房间有些方格是墙壁，如(4，1)，机器人不能经过那儿。
4、有些地方是一旦到达就无法走到出口的,如标记为B的方格,称之为陷阱方格。
5、有些地方是机器人无法到达的的，如标记为A的方格，称之为不可达方格，不可达方	格不包括墙壁所在的位置。
6、如下示例图中，陷阱方格有2个,不可达方格有3个。
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 allCnt墙壁个数，scanf(“%d”, &allCnt))，再循环输入墙壁的下标。我定义一个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 
#include 
#include 

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

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 allCnt = 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", &allCnt);
 for(i = 0; i < allCnt; ++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 %dn", 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;
}