2 条题解
-
10
据题目描述,可以使用动态规划的方法来计算从A到B的最短路径数量。
创建一个二维数组f,大小为(n+1)×(m+1),其中f[i][j]表示从左上角A到位置(i,j)的最短路径数量。
初始化数组f,将f[1][1]设为1,表示从A到A的最短路径数量为1。
然后,从位置(2,1)开始进行状态转移。对于每个位置(i,j),通过以下状态转移方程计算最短路径数量:
- 当i>1且j=1时,f[i][1] = 1;表示从A到第一列其他行的位置的最短路径数量都为1。
- 当i=1且j>1时,f[1][j] = 1;表示从A到第一行其他列的位置的最短路径数量都为1。
- 当i>1且j>1时,f[i][j] = f[i-1][j] + f[i][j-1];表示从A到位置(i,j)的最短路径数量等于从A到位置(i-1,j)和从A到位置(i,j-1)的最短路径数量之和。
最后,得到f[n][m]的值即为从A到B的最短路径数量。
以下是相应的代码实现:
#include<bits/stdc++.h> using namespace std; const int MOD = 100007; int main() { int n, m; cin >> n >> m; vector<vector<int>> f(n + 1, vector<int>(m + 1, 0)); // 初始化f数组,所有元素都设为0 f[1][1] = 1; // 初始化,从A到A的最短路径数量为1 for (int i = 2; i <= n; i++) { f[i][1] = 1; // 从A到第一列其他行的位置的最短路径数量都为1 } for (int j = 2; j <= m; j++) { f[1][j] = 1; // 从A到第一行其他列的位置的最短路径数量都为1 } for (int i = 2; i <= n; i++) { for (int j = 2; j <= m; j++) { f[i][j] = (f[i-1][j] + f[i][j-1]) % MOD; // 状态转移方程 } } cout << f[n][m] << endl; }
-
6
思路
创建二维数组 ,与原始网格的大小相同, 表示从左上角出发到 位置的最少路径数量。显然,。对于 中的其余元素,通过以下状态转移方程计算元素值。
(1)当 且 时,。
(2)当 且 时,
(3)当 且 时,
最后得到 的值即为最少路径数量。
代码
#include<iostream> using namespace std; int f[105][105]; int n, m; const int mod=100007; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { f[i][1] = 1; } for (int j = 1; j <= m; j++) { f[1][j] = 1; } for (int i = 2; i <= n; i++) { for (int j = 2; j <= m; j++) { f[i][j] = (f[i - 1][j]+f[i][j - 1])%mod; } } cout << f[n][m];
}
- 1
信息
- ID
- 352
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- (无)
- 递交数
- 458
- 已通过
- 300
- 上传者