最新华为OD机试真题-公司园区参观路径统计(200分)

大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

感谢大家的订阅➕ 和 喜欢

在线评测链接

=> 公司园区参观路径统计(200分) <=

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

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, int[][] grid) {
        long[][] dp = new long[n][m];
        dp[0][0] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                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];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        long result = uniquePaths(n, m, grid);
        System.out.println(result);
    }
}

• Cpp

#include <iostream>
#include <vector>

using namespace std;

long long uniquePaths(int n, int m, vector<vector<int>>& grid) {
    vector<vector<long long>> dp(n, vector<long long>(m, 0));
    dp[0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            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];
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    auto result = uniquePaths(n, m, grid);
    cout << result << endl;

    return 0;
}