题解 | #挤奶路径2#

知识点：

DFS

分析：

当我们遇到一个二维网格中的位置时，我们有两个选择：向下移动或向右移动。我们可以使用深度优先搜索（DFS）来遍历所有可能的路径。在这个过程中，我们需要跟踪当前路径中是否经过了奶牛的位置。

首先，我们定义一个递归函数`dfs`，它接受当前位置的行索引`row`和列索引`col`，以及一个布尔值`hasCow`，用于标记当前路径是否已经经过了奶牛的位置。

在函数中，我们首先进行边界检查，如果当前位置越界或者遇到了障碍物（值为1），则返回0表示没有路径。然后，我们检查当前位置是否有奶牛（值为2），如果是，则将`hasCow`标记为true。

接下来，我们检查是否到达了右下角，并且当前路径已经经过了奶牛的位置。如果是，我们返回1表示找到一条有效路径。

如果没有到达右下角，我们继续向下和向右递归调用`dfs`函数，分别计算向下和向右的路径数量，并将两者相加，作为当前位置的路径数量。

最后，我们在`调用`dfs`函数，从左上角开始递归遍历整个网格，初始时`hasCow`为false。最终，`countPaths`函数返回的就是从左上角到右下角且经过奶牛位置的路径数量。

编程语言：

C++

完整代码：

    int dfs(vector<vector<int>>& grid, int row, int col, bool hasCow) {
        int m = grid.size();
        int n = grid[0].size();
        // 如果越界或者遇到障碍物，返回0表示没有路径
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 1) {
            return 0;
        }
        // 如果当前位置有奶牛，将hasCow标记为true
        if (grid[row][col] == 2) {
            hasCow = true;
        }
        // 如果到达右下角，且经过奶牛位置，返回1表示找到一条有效路径
        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);
    }