园区参观路径-华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

园区某部门举办了Family Day，邀请员工及其家属参加；将公司园区视为一个矩形，起始园区设置在左上角，终点园区设置在右下角；家属参观园区时，只能向右和向下园区前进；求从起始园区到终点园区会有多少条不同的参观路径；

输入描述：第一行为园区长和宽；后面每一行表示该园区是否可以参观，0表示可以参观，1表示不能参观

输出描述：输出为不同的路径数量

补充说明：

1 <= 园区长 <= 100
1 <= 园区宽 <= 100

示例

示例1

输入：

3 3
0 0 0
0 1 0
0 0 0

输出：2

二.解题思路

1. 初始化二维数组： 创建一个二维数组来表示园区。我们称之为 dp，其中 dp[i][j] 将表示到达位置 (i, j) 的不同路径数。
2. 基本情况： 初始化 dp 数组的左上角。将 dp[0][0] 设置为1，因为到达起始点只有一种方式。
3. 填充第一行和第一列： 遍历 dp 数组的第一行和第一列。对于每个单元格，如果园区中对应的单元格可参观（包含0），则将该单元格的值设置为左方格子和上方格子值之和。
4. 逐行逐列填充： 从第二行和第二列开始，遍历每个单元格。如果园区中对应的单元格可参观，将该单元格的值设置为左方格子和上方格子值之和。
5. 最终结果： 最后，dp[m-1][n-1] 将包含到达终点的不同路径数。

这种动态规划的方法能够有效地计算出从起始园区到终点园区的不同路径数。

JAVA题解代码

import java.util.Scanner;
import java.util.*;
import java.util.st