算法思路

该题与LeetCode 62. 不同路径 和LeetCode 63 . 不同路径II 稍有不同，此题中的机器人可以往上下左右四个方向行走，同时合法路径是将所有无障碍的格子走完的方案。所以该题的思路就不再是DP了，这里采用暴力搜索的思路，通常来说，对于暴搜BFS和DFS都可以，在这里我习惯用DFS，对四个方向进行搜索，同时搜索时对该格子进行标记，当走到终点时，检查是否每个合法的格子都被遍历过。

注意：在进行DFS时先将遍历到的该点进行标记，当函数结束时需要将该标记点还原。

C ++代码

class Solution {
public:
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //四个方向
    int n, m, res;
    pair<int, int> start, end; //起点和终点
    int uniquePathsIII(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();

        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++)
                if (grid[i][j] == 1) //起点
                {
                    start = make_pair(i, j);
                    grid[i][j] = 0;
                }
                else if (grid[i][j] == 2) //终点
                {
                    end = make_pair(i, j);
                    grid[i][j] = 0;
                }

        res = 0;
        dfs(grid, start.first, start.second); //深搜

        return res;
    }

    void dfs(vector<vector<int>>& grid, int x, int y)
    {
        grid[x][y] = 3; //标记，用一个不存在的数即可
        if (x == end.first && y == end.second) //到达终点
        {
            for (int i = 0; i < n; i ++)
                for (int j = 0; j < m; j ++)
                    if (grid[i][j] == 0) //检查是否每个合法点被遍历过
                    {
                        grid[x][y] = 0; //取消当前点标记
                        return;
                    }

            res ++; //记录方案
            grid[x][y] = 0; //回溯取消标记
            return;
        }

        for (int i = 0; i < 4; i ++) //循环方向
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue; //越界
            if (grid[a][b] == 3 || grid[a][b] == -1) continue; //剪枝，已遍历过或不合法
            dfs(grid, a, b);
        }

        grid[x][y] = 0; //回溯
    } 
};