不同路径

leetcode中关于不同路径的题目有三道，在这里整理对比一下

• 起点和终点确定（左上角到右下角）且 前进方式只有向右和向下两种
  • 限制条件
    • 无障碍物 leetcode 62 [DP]
    • 有障碍物 leetcode 63 [DP]
• 起来和终点随机 且 前进方式为传统的四方向
  • 限制条件
    • 每个无障碍的方格都要走才算一条有效路径 leetcode 980 [DFS + 回溯]

62.unique path

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0] = 1; // 注意初值

        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
            {
                if(i) dp [i][j] += dp[i -1][j];
                if(j) dp [i][j] += dp[i][j - 1];
            }

        return dp[m-1][n-1];
    }
};

63.unique path II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

        vector<vector<long long>> dp(m, vector<long long>(n)); // 中间结果可能爆int
        dp[0][0] = !obstacleGrid[0][0];  // 防止入口处就是1

        for(int i = 0; i < m; i++)
            for(int j = 0; j < n ; j++)
            {
                if(obstacleGrid[i][j] == 1) continue;  // 障碍物跳过
                if(i >= 1) dp[i][j] += dp[i - 1][j];  
                if(j >= 1) dp[i][j] += dp[i][j - 1];  
            }

        return dp[m-1][n-1];
    }
};
/*
- 虽然最后结果是int 但是中间结果可能爆int 所以选 longlong
- 入口处的状态 考虑到边界条件 
*/

890.unique path iii
参考了 wzc1995的题解

class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    // 方向数组 上 右 下 左 
    pair<int,int> S, T;  // 起点终点的坐标
    int n, m, res;;

    void dfs(vector<vector<int>>& grid, int x, int y)
    {
        if(x < 0 || x >= n || y < 0 || y >=m || grid[x][y] == 3 || grid[x][y] == -1)
            return ;
        // 超出边界 或者 遇到障碍物 或者 已经走过 则直接返回
        grid[x][y] = 3; 
        // 标记已经走过

        if( x == T.first && y == T.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;
                    }

            //所有空格都走了,结果加1,恢复现场回溯
            res ++;
            grid[x][y] = 0;
            return ;
        }

        // 没有抵达终点 4个方向 dfs
        for(int i = 0;  i < 4; i++)
        {
            int tx = x + dx[i], ty = y + dy[i];
            dfs(grid, tx ,ty);
        }
        //搜索完恢复现场
        grid[x][y] = 0; // 这一步得思考下？？？
    }

    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++)  // 这里 m 第一次写成了n
            {
                if (grid[i][j] == 1)
                {
                    S = make_pair(i, j); //找到起点
                    grid[i][j] = 0;
                }
                if(grid[i][j] == 2)
                {
                    T = make_pair(i, j);
                    grid[i][j] = 0; 
                }
            }

        res = 0;
        dfs(grid, S.first, S.second);
        return res;
    }
};