列表

详情


MGJ9. 方格走法

描述

有一个X*Y的网格,小团要在此网格上从左上角到右下角,只能走格点且只能向右或向下走。请设计一个算法,计算小团有多少种走法。给定两个正整数int x,int y,请返回小团的走法数目。

输入描述

输入包括一行,空格隔开的两个正整数x和y,取值范围[1,10]。

输出描述

输出一行,表示走法的数目

示例1

输入:

3 2

输出:

10

原站题解

C 解法, 执行用时: 1ms, 内存消耗: 368KB, 提交时间: 2020-05-20

#include<stdio.h>
   
long long a[] = {0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000};
   
int main()
{
    int x,y;
    scanf("%d %d", &x, &y);
    printf("%lld", a[x+y]/(a[x]*a[y]));
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 344KB, 提交时间: 2021-09-11

#include <stdio.h>

    int uniquePaths(int m, int n) {
        if(m<1 || n<1)
            return 0;
        if(m==1 || n==1)
            return 1;
        return uniquePaths(m,n-1)+uniquePaths(n,m-1);
    }

int main()
{
    int x,y;
    scanf("%d %d",&x,&y);
    printf("%d\n",uniquePaths(x+1,y+1));
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 352KB, 提交时间: 2019-07-03

#include<stdio.h>
 
long long a[] = {0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000};
 
int main()
{
    int x,y;
    scanf("%d %d", &x, &y);
    printf("%lld", a[x+y]/(a[x]*a[y]));
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 360KB, 提交时间: 2020-05-16

#include<stdio.h>
  
long long a[] = {0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000};
  
int main()
{
    int x,y;
    scanf("%d %d", &x, &y);
    printf("%lld", a[x+y]/(a[x]*a[y]));
    return 0;
}

C++14 解法, 执行用时: 2ms, 内存消耗: 360KB, 提交时间: 2020-03-12

#include<cstdio>
int main(){
    int x,y;
    scanf("%d %d",&x,&y);
    x+=1,y+=1;
    int dp[x][y];
    for(int i=0;i<x;i++) dp[i][0]=1;
    for(int i=0;i<y;i++) dp[0][i]=1;
    for(int i=1;i<x;i++){
        for(int j=1;j<y;j++){
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
            
            
        }
    }
    printf("%d",dp[x-1][y-1]);
    
    
    
    
}

上一题