力扣面试题 - 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;
}