Java 题解 | #挤奶路径2#

import java.util.*;


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

        // 找到所有奶牛的位置
        List<Pair<Integer, Integer>> cowPositions = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (cows[i][j] == 2) {
                    cowPositions.add(new Pair<>(i, j));
                }
            }
        }

        // 如果没有奶牛位置，则无法到达右下角，返回0
        if (cowPositions.isEmpty()) {
            return 0;
        }

        // 分别计算每只奶牛到右下角的路径数，并将这些路径数相乘得到最终答案
        int result = 1;
        int startX = 0;
        int startY = 0;
        for (Pair<Integer, Integer> cowPos : cowPositions) {
            int endX = cowPos.getKey();
            int endY = cowPos.getValue();

            int path = countPaths(cows, startX, startY, endX, endY);
            result *= path;

            startX = endX;
            startY = endY;
        }

        // 计算最后一只奶牛到右下角的路径数
        int path = countPaths(cows, startX, startY, m - 1, n - 1);
        result *= path;

        return result;
    }

    private int countPaths(int[][] cows, int startX, int startY, int endX, int endY) {
        int m = cows.length;
        int n = cows[0].length;

        int[][] dp = new int[m][n];
        dp[startX][startY] = 1;

        for (int i = startX; i <= endX; ++i) {
            for (int j = startY; j <= endY; ++j) {
                if (cows[i][j] == 1) {
                    dp[i][j] = 0; // 遇到障碍物，无法到达
                } else {
                    if (i > startX) {
                        dp[i][j] += dp[i - 1][j];
                    }
                    if (j > startY) {
                        dp[i][j] += dp[i][j - 1];
                    }
                }
            }
        }

        return dp[endX][endY];
    }

    private class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

代码使用了Java编程语言。

这个题目考察了动态规划的基本思想，以及在网格中寻找路径的问题。

了一个网格中包含了三种类型的单元格：0 表示可以通行的空地，1 表示障碍物，2 表示奶牛的位置。你需要从网格的左上角出发，每次只能向右或向下移动，目标是到达网格的右下角，并且必须经过每只牛的位置一次。需要计算一共有多少种不同的路径可以完成这个任务。

代码中的注释提供了对每个部分的解释，以下是简要的解释：

• uniquePathsWithCows 方法：主要函数，计算从左上角到右下角的总路径数，考虑经过每只奶牛的位置。
• countPaths 方法：辅助函数，用动态规划来计算从起始位置到终止位置的路径数。
• Pair 内部类：用来表示坐标对 (x, y)。