A49774. 查找路径
填空题
中等
知识点
题目描述
查找路径
题目描述
有一张 m×n 个小方格的地图，一个机器人位于地图的左上角（如图标记为 Start 的地方），它每步只能向右或者向下移动一格，如果走到右下角的终点（如图标记为 Finish 的地方），有多少种不同的方法？
例如，一个 3×2 的地图，行走的方法数是 3 种，分别是：
右 -> 右 -> 下
右 -> 下 -> 右
下 -> 右 -> 右
输入
两个整数 m (m ≤ 100) 和 n ( n ≤ 100)，代表地图的行数和列数。
输出
一个整数，表示行走的方法数。
样例输入1
8 8
样例输出1
3432
样例输入2
3 3
样例输出2
3
参考答案
#include <iostream>
using namespace std;
const int N = 100;
long long roads[N + 2][N + 2] = {0}; // roads[i][j]: 从起点 (0, 0) 到 (i, j) 的路线总数
int main()
{
int m, n;
cin >> m >> n;
// 第 0 行、第 0 列的格子都只有一条路线
for (int i = 0; i < m; ++i)
{
roads[i][0] = 1;
}
for (int i = 0; i < n; ++i)
{
roads[0][i] = 1;
}
for (int i = 1; i < m; ++i)
{
for (int j = 1; j < n; ++j)
{
roads[i][j] = roads[i - 1][j] + roads[i][j - 1];
}
}
cout << roads[m - 1][n - 1] << endl;
return 0;
}
上一题
下一题