题目：
1、房间由X*Y的方格组成，例如下图为6*4的大小。每一个方格以坐标(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 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; //不是墙壁 也不是陷阱 就改为1if(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;}
