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

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

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1056

🌍 评测功能需要 订阅专栏 后私信联系清隆解锁～

🍓OJ题目截图

🏠 公司园区参观路径统计

问题描述

K小姐所在公司举办了 Family Day 活动，邀请员工及其家属参观公司园区。将公司园区视为一个 $n\times m$ 的矩形网格，起始位置在左上角，终点位置在右下角。家属参观园区时，只能向右或向下移动。园区中有些位置设有闸机，无法通行。请问，从起始位置到终点位置，一共有多少种不同的参观路径？

输入格式

第一行包含两个正整数 $n$ 和 $m$，分别表示园区的行数和列数。
接下来 $n$ 行，每行包含 $m$ 个空格分隔的数字，数字为 $0$ 表示该位置可以通行，数字为 $1$ 表示该位置无法通行。

输出格式

输出一个整数，表示从起始位置到终点位置的不同参观路径数量。

样例输入

3 3
0 0 0
0 1 0
0 0 0

样例输出

2

数据范围

$1\le n,m\le 100$

题解

本题可以使用动态规划的思想求解。设 $dp[i][j]$ 表示从起始位置到达位置 $(i,j)$ 的不同路径数量。对于每个位置 $(i,j)$，如果该位置可以通行，那么到达该位置的路径数量等于到达其上方位置 $(i-1,j)$ 和左侧位置 $(i,j-1)$ 的路径数量之和。

初始条件：$dp[0][0]=1$，表示起始位置的路径数量为 $1$。
状态转移方程：

• 如果位置 $(i,j)$ 可以通行，即 $grid[i][j]=0$，则 $dp[i][j]=dp[i-1][j]+dp[i][j-1]$。
• 如果位置 $(i,j)$ 无法通行，即 $grid[i][j]=1$，则 $dp[i][j]=0$。

最终答案为 $dp[n-1][m-1]$，表示从起始位置到终点位置的不同路径数量。

时间复杂度：$O(nm)$，需要遍历整个网格。
空间复杂度：$O(nm)$，需要创建一个二维数组存储状态值。

参考代码

• 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;
}