题解 | #挤奶路径2#

考察的知识点：动态规划；

解答方法分析：

1. 函数uniquePathsWithCows首先判断输入的矩阵cows是否为空或者其中的行或列是否为空，如果是，则返回0。调用dfs函数进行DFS搜索，初始时，行和列的引都是0，hasCow参数为false。
2. dfs函数首先获取输入矩阵的维度m和n。然后，它查当前坐标（row，col）是否超出矩阵范围或者是否遇到了障碍物，如果是，则返回0。如果当前位置上有一头牛，则将hasCow参数标记为true。
3. 检查当前坐标是否为终点，且hasCow为true，如果是，则返回1，表示找到了一条符合条件的路径。
4. 递归调用dfs函数，分别向下和向右移动，并将hasCow参数传递下去，计算从下一格和右一格出发的路径数量，然后将两者相加作为当前格子的所有可能路径数量，并返回这个值。
5. 函数uniquePathsWithCows返回dfs函数的结果，即起点到终点的所有路径数量。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    int dfs(vector<vector<int>>& grid, int row, int col, bool hasCow) {
        int m = grid.size();
        int n = grid[0].size();
        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;
    }
    int uniquePathsWithCows(vector<vector<int> >& cows) {
        if (cows.empty() || cows[0].empty()) {
            return 0;
        }
        return dfs(cows, 0, 0, false);
    }
};