一. 题目-园区参观路径
园区某部门举办了Family Day，邀请员工及其家属参加；将公司园区视为一个矩形，起始园区设置在左上角，终点园区设置在右下角；家属参观园区时，只能向右和向下园区前进；求从起始园区到终点园区会有多少条不同的参观路径；
输入描述：第一行为园区长和宽；后面每一行表示该园区是否可以参观，0表示可以参观，1表示不能参观
输出描述：输出为不同的路径数量
补充说明：
1 <= 园区长 <= 100
1 <= 园区宽 <= 100
示例
示例1
输入：3 3
0 0 0
0 1 0
0 0 0
输出：2
二.解题思路
当解决这个问题时，可以采取以下思路：
-
初始化二维数组： 创建一个二维数组来表示园区。我们称之为
dp，其中dp[i][j]将表示到达位置(i, j)的不同路径数。 -
基本情况： 初始化
dp数组的左上角。将dp[0][0]设置为1，因为到达起始点只有一种方式。 -
填充第一行和第一列： 遍历
dp数组的第一行和第一列。对于每个单元格，如果园区中对应的单元格可参观（包含0），则将该单元格的值设置为左方格子和上方格子值之和。 -
逐行逐列填充： 从第二行和第二列开始，遍历每个单元格。如果园区中对应的单元格可参观，将该单元格的值设置为左方格子和上方格子值之和。
-
最终结果： 最后，
dp[m-1][n-1]将包含到达终点的不同路径数。
这种动态规划的方法能够有效地计算出从起始园区到终点园区的不同路径数。
三.题解代码
Python题解代码
import sys
def getRoadNums(matrix,M,N):
tmp=[[1]*N]*M
for i in range(M):
for j in range(N):
shang= matrix[i-1][j] if i>0 else '-1'
zuo = matrix[i][j-1] if j>0 else '-1'
if i==0 and j==0:
continue
if matrix[i][j]=='1':
tmp[i][j]=0
else:
shang_num=tmp[i-1][j] if shang=='0' else 0
zuo_num=tmp[i][j-1] if zuo=='0' else 0
tmp[i][j]=shang_num+zuo_num
# print(tmp)
return tmp[M-1][N-1]
if __name__=='__main__':
matrix=[]
M,N=list(map(int,sys.stdin.readline().strip().split()))
for line in sys.stdin:
a = line.split()
matrix.append(a)
print(getRoadNums(matrix,M,N))
JAVA题解代码
import java.util.Scanner;
import java.util.*;
import java.util.stream.Stream;
import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][] matrix = new int[n][m];
int[][] dp = new int[n+1][m+1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = in.nextInt();
}
}
for (int i = 0; i < n+1; i++) {
for (int j = 0; j < m+1; j++) {
dp[i][j] = 0;
}
}
dp[0][1] = 1;
for (int i = 1; i < n+1; i++) {
for (int j = 1; j < m+1; j++) {
if (matrix[i - 1][j - 1] == 0){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
System.out.println(dp[n][m]);
}
}
C/C++题解代码
#include<bits/stdc++.h> // 包含常用的标准库
using namespace std;
const int N = 1010; // 定义常量N为1010
long long g[N][N], f[N][N]; // 定义二维数组g和f
int n, m; // 定义变量n和m
int main() {
cin >> n >> m; // 从标准输入流读入n和m的值
for (int i = 0; i < n; i++) { // 遍历n次
for (int j = 0; j < m; j++) { // 遍历m次
cin >> g[i][j]; // 从标准输入流读入g[i][j]的值
}
}
for (int i = 0; i < m; i++) { // 遍历m次
if (g[0][i]) { // 如果g[0][i]为真
break; // 跳出循环
}
f[0][i] = 1; // 将f[0][i]的值设为1
}
for (int i = 0; i < n; i++) { // 遍历n次
if (g[i][0]) { // 如果g[i][0]为真
break; // 跳出循环
}
f[i][0] = 1; // 将f[i][0]的值设为1
}
for (int i = 1; i < n; i++) { // 遍历n-1次
for (int j = 1; j < m; j++) { // 遍历m-1次
if (g[i][j]) f[i][j] = 0; // 如果g[i][j]为真，将f[i][j]的值设为0
else f[i][j] = f[i - 1][j] + f[i][j - 1]; // 否则，将f[i][j]的值设为f[i-1][j]+f[i][j-1]
}
}
cout << f[n - 1][m - 1] << endl; // 输出f[n-1][m-1]的值
return 0; // 返回0
}
JS题解代码
const readline = require('readline'); // 引入readline模块
const rl = readline.createInterface({ // 创建readline接口
input: process.stdin, // 设置输入流
output: process.stdout // 设置输出流
});
let n, m, g, f; // 定义变量n, m, g, f
rl.on('line', (line) => { // 监听输入事件
if (!n) { // 如果n未定义
[n, m] = line.split(' ').map(Number); // 将输入按空格分割并转为数字，赋值给n, m
g = new Array(n).fill(0).map(() => []); // 创建二维数组g
} else { // 否则
const values = line.split(' ').map(Number); // 将输入按空格分割并转为数字，赋值给values
for (let i = 0; i < m; i++) { // 遍历m次
g[n - 1].push(values[i]); // 将values[i]的值加入g[n-1]中
}
n--; // n减1
if (n === 0) { // 如果n为0
f = new Array(g.length).fill(0).map(() => new Array(g[0].length).fill(0)); // 创建二维数组f
for (let i = 0; i < m; i++) { // 遍历m次
if (g[0][i]) { // 如果g[0][i]为真
break; // 跳出循环
}
f[0][i] = 1; // 将f[0][i]的值设为1
}
for (let i = 0; i < g.length; i++) { // 遍历g.length次
if (g[i][0]) { // 如果g[i][0]为真
break; // 跳出循环
}
f[i][0] = 1; // 将f[i][0]的值设为1
}
for (let i = 1; i < g.length; i++) { // 遍历g.length-1次
for (let j = 1; j < g[0].length; j++) { // 遍历g[0].length-1次
if (g[i][j]) { // 如果g[i][j]为真
f[i][j] = 0; // 将f[i][j]的值设为0
} else {
f[i][j] = f[i - 1][j] + f[i][j - 1]; // 否则，将f[i][j]的值设为f[i-1][j]+f[i][j-1]
}
}
}
console.log(f[g.length - 1][g[0].length - 1]); // 输出f[g.length-1][g[0].length-1]的值
rl.close(); // 关闭readline接口
}
}
});
四.代码讲解(Java&Python&C++&JS分别讲解)
Python题解代码解析
这段Python代码用于解决从起始点到终点的不同路径数量问题。以下是代码的主要思路：
-
函数定义：
getRoadNums函数接收三个参数：matrix表示园区的矩阵，M和N表示园区的长和宽。 -
初始化： 创建一个名为
tmp的二维数组，用于存储每个位置的可达路径数，初始值全部设置为1。 -
遍历园区： 使用两个嵌套的循环遍历园区矩阵。对于每个位置
(i, j)，分别获取其上方格子的值shang和左方格子的值zuo，并根据条件判断是否更新tmp[i][j]的值。 -
返回结果： 函数返回
tmp[M-1][N-1]，即从起始园区到终点园区的不同路径数量。
JAVA题解代码解析
这段Java代码同样用于解决从起始点到终点的不同路径数量问题。以下是代码的主要思路：
-
主函数：
main方法从标准输入读取园区的长n和宽m，以及园区的矩阵matrix。 -
初始化数组： 创建两个二维数组
matrix和dp，其中matrix用于存储园区的矩阵，dp用于存储每个位置的可达路径数。初始化dp数组的第一行和第一列。 -
动态规划： 使用两个嵌套的循环遍历
matrix，根据动态规划的思想更新dp数组。最终，dp[n][m]将包含从起始点到终点的不同路径数量。
C/C++题解代码解析
这段C/C++代码也用于解决从起始点到终点的不同路径数量问题。以下是代码的主要思路：
-
包含头文件： 引入
bits/stdc++.h头文件，该头文件包含了常用的标准库。 -
定义数组： 定义两个二维数组
g和f，其中g存储园区的矩阵，f存储每个位置的可达路径数。 -
读取输入： 从标准输入读取园区的长
n和宽m，以及园区的矩阵g。 -
动态规划： 使用两个嵌套的循环遍历
g，根据动态规划的思想更新f数组。最终，f[n-1][m-1]将包含从起始点到终点的不同路径数量。
JS题解代码解析
这段JavaScript代码解决了相同的问题。以下是代码的主要思路：
-
读取输入： 使用
readline模块逐行读取输入。首先读取园区的长n和宽m，然后逐行读取园区的矩阵matrix。 -
初始化数组： 创建两个二维数组
matrix和dp，其中matrix存储园区的矩阵，dp存储每个位置的可达路径数。初始化dp数组的第一行和第一列。 -
动态规划： 使用两个嵌套的循环遍历
matrix，根据动态规划的思想更新dp数组。最终，dp[g.length-1][g[0].length-1]将包含从起始点到终点的不同路径数量。