top1编程
← 返回题目
题解

移动路线

1 条题解

  • 0
    @ 2026-7-29 20:22:38
    /*
    【解题思路:蚂蚁走格子,只能从左边或下面来】
    小朋友们,这道题有一只蚂蚁,它从左下角出发,要走到右上角。
    因为蚂蚁只能向上或向右走,所以每个格子的路线数,都可以从它的“下面”和“左边”推出来。
    我们用 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