题解 | #挤奶路径2#

解法一:深度优先搜索

1. 先判空
2. 从cows[0][0]开始深度优先遍历,若越界或障碍(不可达)返回0
3. 若经过唯一的奶牛将路径奶牛标记为true;
4. 抵达右下角时且经过奶牛时返回1
5. 递归向右一步路径数和向下一步路径数
6. 二者和即为经过奶牛的总的路径数

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型二维数组 
     * @return int整型
     */
    public int uniquePathsWithCows (int[][] cows) {
        if(cows.length==0 || cows[0].length==0){
            return 0;
        }
        return dfs(cows,0,0,false);
    }

    private int dfs(int[][] grid,int row,int col,boolean hasCow){
        int m = grid.length;
        int n = grid[0].length;
        //越界或遇到障碍物
        if(row<0||row>=m||col<0||col>=n||grid[row][col]==1){
            return 0;
        }
        //经过奶牛
        if(grid[row][col]==2){
            hasCow = true;
        }
        // 到达右下角
        if(row==m-1&&col==n-1&&hasCow){
            return 1;
        }
        // 向下
        int downPaths = dfs(grid,row+1,col,hasCow);
        // 向右
        int rightPaths = dfs(grid,row,col+1,hasCow);
        // 统计路径
        return downPaths+rightPaths;
    }
}

解法二:动态规划

1. 判空
2. 设计dp数组dp[i][j]代表由cows[start_i][start_j]->cows[i][j]的路径数
3. 转移方程:dp[i][j]=dp[i-1][j]+dp[i][j-1],注意防止越界,起点dp[start_i][start_j]=1
4. 经过奶牛的位置到达右下角的路径数=左上角->奶牛路径数*奶牛->右下角路径数

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型二维数组
     * @return int整型
     */
    public int uniquePathsWithCows (int[][] cows) {
        int m = cows.length;
        int n = cows[0].length;
        if (m == 0 || n == 0) {
            return 0;
        }
        // 记录奶牛位置
        int cow_i = 0,cow_j = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(cows[i][j]==2){
                    cow_i=i;
                    cow_j=j;
                    break;
                }
            }
        }
        // 经过奶牛的位置到达右下角=左上角->奶牛*奶牛->右下角
        return uniquePath(cows,0,0,cow_i,cow_j)*uniquePath(cows,cow_i,cow_j,m-1,n-1);
    }

    private int uniquePath(int[][] cows, int start_i, int start_j, int end_i,
                           int end_j) {
        int m = cows.length;
        int n = cows[0].length;
        // dp[i][j]代表由cows[start_i][start_j]->cows[i][j]有几条路径
        int[][] dp = new int[m][n];
        // 起点初始化
        dp[start_i][start_j] = 1;
        for (int i = start_i; i <= end_i; i++) {
            for (int j = start_j; j <= end_j; j++) {
                // 不更改起点
                if (i != start_i || j != start_j) {
                    // 不是障碍物
                    if (cows[i][j] != 1) {
                        // 避免越界
                        dp[i][j] = (i > 0 ? dp[i - 1][j] : 0) + (j > 0 ? dp[i][j - 1] : 0);
                    }
                }
            }
        }
        return dp[end_i][end_j];
    }
}