题解
移动路线
1 条题解
-
0
/* 【解题思路:蚂蚁走格子,只能从左边或下面来】 小朋友们,这道题有一只蚂蚁,它从左下角出发,要走到右上角。 因为蚂蚁只能向上或向右走,所以每个格子的路线数,都可以从它的“下面”和“左边”推出来。 我们用 a[i][j] 表示:蚂蚁走到第 i 行第 j 列这个格子,一共有多少种不同路线。 第一列的格子,只能一直向上走,所以每个格子的走法都是 1 种。 第一行的格子,只能一直向右走,所以每个格子的走法也是 1 种。 中间的格子 a[i][j] 只能从两个地方来: 1. 从下面的格子 a[i-1][j] 向上走一步。 2. 从左边的格子 a[i][j-1] 向右走一步。 所以:a[i][j] = a[i-1][j] + a[i][j-1] 最后输出右上角 a[m][n],也就是第 m 行第 n 列的路线数。 */ #include<bits/stdc++.h> using namespace std; long long a[21][21]; // a[i][j] 表示走到第 i 行第 j 列有多少种路线 int m,n; // m 表示行数,n 表示列数 int main(){ cin>>m>>n; // 第一列:只能一直向上走,所以每个格子都只有 1 种走法 for(int i=1;i<=m;i++){ a[i][1]=1; } // 第一行:只能一直向右走,所以每个格子也只有 1 种走法 for(int j=1;j<=n;j++){ a[1][j]=1; } // 从第 2 行第 2 列开始算中间格子 // 每个格子的路线数 = 从下面来的路线数 + 从左边来的路线数 for(int i=2;i<=m;i++){ for(int j=2;j<=n;j++){ a[i][j]=a[i-1][j]+a[i][j-1]; } } // 输出走到右上角,也就是第 m 行第 n 列的路线数 cout<<a[m][n]<<endl; return 0; }
- 1