华为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; }