园区参观路径 - 华为OD统一考试

本文主要是介绍园区参观路径 - 华为OD统一考试，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

园区某部门举办了Family Day，邀请员工及其家属参加；

将公司园区视为一个矩形，起始园区设置在左上角，终点园区设置在右下角；

家属参观园区时，只能向右和向下园区前进，求从起始园区到终点园区会有多少条。

输入描述

输入第一行为园区的长和宽；

接下来每一行表示该园区是否可以参观，0表示可以参观，1表示不可以参观。

输出描述

输出为不同路径的数量

示例1

题解

经典的动态规划问题。

1、状态定义：
dp[i][j] 表示走到格子 (i,j) 的方法数。

2、状态转移：

如果网格 (i,j) 上有障碍物，则 dp[i][j] 值为 0，表示走到该格子的方法数为 0；
否则网格 (i,j) 可以从网格 (i−1,j) 或者网格 (i,j−1) 走过来，因此走到该格子的方法数为走到网格 (i−1,j) 和网格 (i,j−1) 的方法数之和，即 dp[i,j]=dp[i−1,j]+dp[i,j−1]。

Java

import java.util.Scanner;
/*** @author code5bug*/
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取输入int l = scanner.nextInt(), w = scanner.nextInt();int[][] garden = new int[l][w];for (int i = 0; i < l; i++) {for (int j = 0; j < w; j++) {garden[i][j] = scanner.nextInt();}}// 初始化动态规划数组int[][] dp = new int[l + 1][w + 1];dp[0][1] = 1;// 动态规划计算for (int r = 0; r < l; r++) {for (int c = 0; c < w; c++) {if (garden[r][c] == 1) {dp[r + 1][c + 1] = 0;} else {dp[r + 1][c + 1] = dp[r][c + 1] + dp[r + 1][c];}}}// 输出结果System.out.println(dp[l][w]);}
}

Python

l, w = map(int, input().split())
garden = [list(map(int, input().split())) for _ in range(l)]dp = [[0] * (w + 1) for _ in range(l + 1)]
dp[0][1] = 1for r in range(l):for c in range(w):if garden[r][c] == 1:dp[r+1][c+1] = 0else:dp[r+1][c+1] = dp[r][c+1] + dp[r+1][c]print(dp[l][w])

C++

#include <iostream>
#include <vector>using namespace std;int main() {// 读取输入int l, w;cin >> l >> w;vector<vector<int>> garden(l, vector<int>(w));for (int i = 0; i < l; i++) {for (int j = 0; j < w; j++) {cin >> garden[i][j];}}// 初始化动态规划数组vector<vector<int>> dp(l + 1, vector<int>(w + 1, 0));dp[0][1] = 1;// 动态规划计算for (int r = 0; r < l; r++) {for (int c = 0; c < w; c++) {if (garden[r][c] == 1) {dp[r + 1][c + 1] = 0;} else {dp[r + 1][c + 1] = dp[r][c + 1] + dp[r + 1][c];}}}// 输出结果cout << dp[l][w] << endl;return 0;
}