最新华为OD机试真题-公司园区参观路径统计(200分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🏠 公司园区参观路径统计
问题描述
K小姐所在公司举办了 Family Day 活动,邀请员工及其家属参观公司园区。将公司园区视为一个 的矩形网格,起始位置在左上角,终点位置在右下角。家属参观园区时,只能向右或向下移动。园区中有些位置设有闸机,无法通行。请问,从起始位置到终点位置,一共有多少种不同的参观路径?
输入格式
第一行包含两个正整数 和 ,分别表示园区的行数和列数。 接下来 行,每行包含 个空格分隔的数字,数字为 表示该位置可以通行,数字为 表示该位置无法通行。
输出格式
输出一个整数,表示从起始位置到终点位置的不同参观路径数量。
样例输入
3 3
0 0 0
0 1 0
0 0 0
样例输出
2
数据范围
题解
本题可以使用动态规划的思想求解。设 表示从起始位置到达位置 的不同路径数量。对于每个位置 ,如果该位置可以通行,那么到达该位置的路径数量等于到达其上方位置 和左侧位置 的路径数量之和。
初始条件:,表示起始位置的路径数量为 。 状态转移方程:
- 如果位置 可以通行,即 ,则 。
- 如果位置 无法通行,即 ,则 。
最终答案为 ,表示从起始位置到终点位置的不同路径数量。
时间复杂度:,需要遍历整个网格。 空间复杂度:,需要创建一个二维数组存储状态值。
参考代码
- Python
def uniquePaths(n, m, grid):
dp = [[0] * m for _ in range(n)]
dp[0][0] = 1
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
dp[i][j] = 0
else:
if i > 0:
dp[i][j] += dp[i - 1][j]
if j > 0:
dp[i][j] += dp[i][j - 1]
return dp[n - 1][m - 1]
n, m = map(int, input().split())
grid = []
for _ in range(n):
row = list(map(int, input().split()))
grid.append(row)
result = uniquePaths(n, m, grid)
print(result)
- Java
import java.util.Scanner;
public class Main {
public static long uniquePaths(int n, int m, in
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测