题解 | #牛牛的迷宫探索#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param maze char字符型二维数组 
     * @return int整型
     */
    public int uniquePaths (char[][] maze) {
        // write code here
         int n = maze.length;
        int m = maze[0].length;
        
        int[][] dp = new int[n][m];
        dp[0][0] = 1;
        
        // 初始化第一行和第一列
        for (int j = 1; j < m; j++) {
            if (maze[0][j] == '#') {
                break;
            }
            dp[0][j] = 1;
        }
        for (int i = 1; i < n; i++) {
            if (maze[i][0] == '#') {
                break;
            }
            dp[i][0] = 1;
        }
        
        // 动态规划计算路径数量
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (maze[i][j] != '#') {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        
        return dp[n-1][m-1];
    }
}

首先，创建一个大小为 n × m 的二维数组 dp，并将每个元素初始化为 0。dp[i][j] 表示从起点到达坐标(i, j)的路径数量。

然后，使用动态规划的思路来计算路径数量。由于动物牛只能向右或向下移动，所以对于迷宫中的第一行和第一列，动物牛只有一种路径可以到达。因此，将 dp[0][j] 和 dp[i][0] 初始化为 1。

接下来，对于其他的位置(i, j)，它的路径数量等于从上方的单元格 (i-1, j) 和左侧的单元格 (i, j-1) 到达 (i, j) 的路径数量之和，即 dp[i][j] = dp[i-1][j] + dp[i][j-1]。但是，如果当前单元格是墙壁，那么它不能作为路径的一部分，因此将 dp[i][j] 设为 0。

最后，返回最右下角单元格的路径数量，即 dp[n-1][m-1]。