华为OD机试：园区参观路径

题目描述

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

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

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

输入描述

第一行为园区的长和宽；

后面每一行表示该园区是否可以参观，0表示可以参观，1表示不能参观

输出描述

输出为不同的路径数量

用例

题目解析

1.首先将输入的园区地图转换为二维数组。

2.初始化一个二维数组dp，用于记录从起点到每个栅格的路径数量。

3.遍历园区地图，对于每个栅格，计算从起点到该栅格的路径数量，即取其上方和左方两个方向的路径数量之和。

4.更新dp数组中对应栅格的值为计算出的路径数量。

5.继续遍历下一个栅格，直到遍历完所有栅格。

6.返回dp数组中终点的值作为结果。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
const readline = async () => (await rl[Symbol.asyncIterator]().next()).value;

(async function () {
  const [n, m] = (await readline()).split(" ").map(Number);

  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix.push((await readline()).split(" ").map(Number));
  }

  if (matrix[0][0] == 1 || matrix[n - 1][m - 1] == 1) {
    console.log(0);
    return;
  }

  const dp = new Array(n).fill(0).map(() => new Array(m).fill(0));
  dp[0][0] = 1;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (matrix[i][j] == 1) continue;

      if (i > 0) {
        dp[i][j] += dp[i - 1][j];
      }

      if (j > 0) {
        dp[i][j] += dp[i][j - 1];
      }
    }
  }

  console.log(dp[n - 1][m - 1]);
})();

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();  
    int m = sc.nextInt();  

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

    if (matrix[0][0] == 1 || matrix[n - 1][m - 1] == 1) {
      System.out.println(0);
      return;
    }

    long[][] dp = calculatePaths(matrix, n, m);

    System.out.println(dp[n - 1][m - 1]);
  }

  private static long[][] calculatePaths(int[][] matrix, int n, int m) {
    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 (matrix[i][j] == 1) continue;

        if (i > 0) {
          dp[i][j] += dp[i - 1][j];
        }

        if (j > 0) {
          dp[i][j] += dp[i][j - 1];
        }
      }
    }

    return dp;
  }
}

Python算法源码

 
def getResult(matrix):
    n, m = len(matrix), len(matrix[0])
    if matrix[0][0] == 1 or matrix[n - 1][m - 1] == 1:
        return 0

    dp = [[0 for _ in range(m)] for _ in range(n)]
    dp[0][0] = 1

    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1:
                continue

            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())   
matrix = [list(map(int, input().split())) for _ in range(n)]   
print(getResult(matrix))

C算法源码

#include <stdio.h>
#include <stdlib.h>

int main() {
    size_t n, m;
    scanf("%zu %zu", &n, &m);

    int *matrix = (int *)malloc(n * m * sizeof(int));
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < m; ++j) {
            scanf("%d", &matrix[i * m + j]);
        }
    }

    if (matrix[0] == 1 || matrix[(n - 1) * m + m - 1] == 1) {
        puts("0");
        free(matrix);
        return 0;
    }

    long *dp = (long *)calloc(n * m, sizeof(long));
    dp[0] = 1;

    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < m; ++j) {
            if (matrix[i * m + j] & 1) continue;

            if (i > 0) {
                dp[i * m + j] += dp[(i - 1) * m + j];
            }

            if (j > 0) {
                dp[i * m + j] += dp[i * m + j - 1];
            }
        }
    }

    printf("%ld\n", dp[(n - 1) * m + m - 1]);

    free(matrix);
    free(dp);
    return 0;
}