力扣面试题 - 40 迷路的机器人 C语言解法

题目：

设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。

网格中的障碍物和空位置分别用 1 和 0 来表示。

返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。

示例 1:

输入:
[[0,0,0],[0,1,0],[0,0,0]
]
输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]
解释: 
输入中标粗的位置即为输出表示的路径，即
0行0列（左上角） -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列（右下角）

说明：r 和 c 的值均不超过 100。

思路：

1. 深度优先（DFS）寻找终点。
2. 使用visited数组记录走过的路径
3. 发现不可行的路径就回溯，直到到达终点

以下C代码有参考题解区大佬：taopi

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/int visited[100][100];
int DFS(int** obstacleGrid, int r, int c, int x, int y, int** ret, int* len) {// 碰到边界或者障碍，或者重复到达if(x >= r || y >= c || obstacleGrid[x][y] || visited[x][y]){return 0;}ret[*len][0] = x;ret[(*len)++][1] = y;// 到达终点if(x == r - 1 && y == c - 1) {return 1;}visited[x][y] = 1;// 下或者右 有路可走if(DFS(obstacleGrid, r, c, x, y + 1, ret, len) || DFS(obstacleGrid, r, c, x + 1, y, ret, len)){return 1;}// 无路可走，回溯(*len)--;return 0;
}int** pathWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize, int* returnSize, int** returnColumnSizes) {*returnSize = 0;int r = obstacleGridSize, c = *obstacleGridColSize;if(r == 0 || c == 0 || obstacleGrid[0][0] || obstacleGrid[r-1][c-1]) {return NULL;}int** ret = malloc(sizeof(int*) * (r + c));for(int i = 0; i < r + c; i++){ret[i] = malloc(sizeof(int) * 2);}int len = 0;memset(visited, 0, sizeof(visited));if(DFS(obstacleGrid, r, c, 0, 0, ret, &len)) {*returnSize = len;*returnColumnSizes = (int*)malloc(sizeof(int) * len);for(int i = 0; i < len; i++) {(*returnColumnSizes)[i] = 2;}return ret;}for(int i = 0; i < r + c; i++){free(ret[i]);}free(ret);return NULL;
}