首页 > 试题广场 >

走方格的方案数

[编程题]走方格的方案数

热度指数：129307 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

注：沿棋盘格之间的边缘线行走

数据范围： $1 \le n,m \le 8 \$

输入描述:

输入两个正整数n和m，用空格隔开。(1≤n,m≤8)

输出描述:

输出一行结果

示例1

输入

2 2

输出

算法知识视频讲解

Java

牛客834002708号

import java.util.*;
public class Main {
    static int sum = 0;    // 走法
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            int n = in.nextInt();
            int m = in.nextInt();
            sum = 0;        // 每个案例都需要重新置0
            Test(0,0,n,m);  // 递归走方格
            System.out.println(sum);
        }
    }
    public static void Test(int i, int j, int n, int m){  // 递归走方格
        if(i==n && j==m){  // 走到终点即得到一种走法
            ++sum;
            return;
        }
        if(i+1 <= n){      // 往下走
            Test(i+1,j,n,m);
        }
        if(j+1 <= m){      // 往右走
            Test(i,j+1,n,m);
        }
    }
}

发表于 2021-08-14 15:52:31 回复(0)

小陈也只是想要一个实习罢了

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    public static int findWays(int m,int n){
        int[] rec=new int[n];
        rec[0]=1;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(j==0) rec[j]=rec[j];
                else if(i==0) rec[j]=rec[j-1];
                else rec[j]=rec[j-1]+rec[j];
            }
        }
        return rec[n-1];
    }

    public static void main(String[] args)throws IOException {
        //读入和输出的方式要注意，使用bufferedReader中的readLine可以很好知道是否到了末尾
        BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
        String line=null;
        while((line=bReader.readLine())!=null) {
            int n=Integer.valueOf(line.substring(0,line.indexOf(" ")));
            int m=Integer.valueOf(line.substring(line.indexOf(" ")+1));
            System.out.println(findWays(n+1, m+1));
        }
    }
}

发表于 2020-06-08 12:06:52 回复(1)

棉花汤

递归调用

#include<iostream>

using namespace std;

int f(int n,int m)
{
	if(n==1)
		return (m+1);
	else if(m==1)
		return (n+1);
	else
		return f(n,m-1)+f(n-1,m);
}

int main(int argc, char const *argv[])
{
	int n,m;
	while(cin>>n>>m)
	{
		cout<<f(n,m)<<endl;
	}

	return 0;
}

发表于 2016-07-08 00:08:21 回复(0)

牛客312540312号

#include<stdio.h>

int main()
{
int a, b;
while(scanf("%d %d",&a,&b) != EOF)
{
int c = 1, d = 1;
for(int i = 1; i <= a; i++)
{
c *= i;
}
for(int j = b + 1; j <= a + b; j++)
{
d *= j;
}
printf("%d\n", d/c);
}
}

发表于 2021-08-11 20:24:54 回复(0)

C++

yzbyzb

#include <iostream>
using namespace std;

int f(int a){
if(a==1) return 1;
return a*f(a-1);
}

int main(){
int n,m;
while(cin>>n>>m){
cout<<f(n+m)/f(n)/f(m)<<'\n';
}
}

发表于 2021-07-20 00:04:37 回复(0)

牛客-120抢救中心

import java.util.Scanner;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            System.out.println(calc(m,n));
        }
    }
    public static int calc(int m, int n) {
        if(m==0 || n==0) {
            return 1;
        }
        return calc(m-1,n)+calc(m,n-1);
    }
}

发表于 2018-10-09 21:35:07 回复(0)

Python 3

来个offer叭！

get_str = input().split(' ')
n, m = int(get_str[0]), int(get_str[1])
# (n+1)*(m+1)的二维dp数组
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n+1):
    for j in range(m+1):
        # dp数组初始化
        # 原点时0种走法
        if i==0 and j==0:
            dp[i][j] = 0
        # 从原点向下走一步共1种走法
        # elif i==0 and j==1:
        # 这里可以考虑优化？当退到左边界或上边界时仅剩一种走法
        elif i==0:
            dp[i][j] = 1
        # 从原点向右走一步共1种走法
        # elif i==1 and j==0:
        elif j==0:
            dp[i][j] = 1
        # [i][j]点的走法=左边一个点走法+上面一个点的走法
        # 即：dp[i][j] = dp[i-1][j] + dp[i][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[n][m])

发表于 2022-07-30 17:46:31 回复(0)

C++

李艳飞

#include <iostream>

using namespace std;

int fun(int num);

int main()
{
    int m=0, n=0;
    cin>>m>>n;
    cout<<fun(n+m)/(fun(m)*fun(n))<<endl;
    return 0;
}

int fun(int num)
{
    int sum=1;
    for(int i=2;i<=num;i++)
    {
        sum*=i;
    }
    return sum;
}

发表于 2022-05-12 20:49:29 回复(1)

Java

笨糕sama

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        while (sc.hasNextInt()){

            int n = sc.nextInt();
            int m = sc.nextInt();
            int countUp = n;
            int countDown = n+m;
            int num = n;
            int zzz = n+m;
//            for (int a=n;a>1;--a){
//                    countUp = countUp*(a-1);
//                    countDown = countDown*(--countDown);
//            }
            while (num>1){
                countUp = countUp*(num-1);
                countDown = countDown*(zzz-1);
                num--;
                zzz--;
            }
            int count = countDown/countUp;

            System.out.println(count);
        }

    }
}

发表于 2021-11-26 01:19:31 回复(0)

Java

AlexWenn

方法1：
//数学方法，相当于一共要走（n+m)步，其中往右走要走n步，问题是在（n+m）步里哪些步是
//往右走。相当于在（n+m）个中取m个有多少种组合的问题。
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();

            System.out.println(combination(n, n+m));
        }
        sc.close();
    }

    public static int combination(int m, int n){//排列C(m,n)
        int above = factorial(n);
        int below = factorial(n-m) * factorial(m);
        return above / below;
    }

    public static int factorial(int n){//阶乘
        if(n>1){
            return n*factorial(n-1);
        }
        return n;
    }
}

方法2：把问题解法定为f(n,m),从左上角第1个点开始，如果往右走1步，剩下的问题就变成了f(n-1,m); 如果一开始往下走一步，剩下的问题就变成f(n,m-1), 一直递归，就有了f(n,m)=f(n-1,m)+f(n,m-1)。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()){
            int m = sc.nextInt();
            int n = sc.nextInt();
            System.out.println(count(m,n));
        }

        sc.close();
    }

    public static int count(int m, int n){

        if(m==0 || n==0){
            return 1;
        }

        return count(m-1,n)+count(m,n-1);


    }

}

发表于 2021-10-27 10:46:50 回复(0)

彩虹桥的梦

动态规划：

while True:
    try:
        n,m = map(int, input().split())

        dp = [[1 for _ in range(m+1)] for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                temp = dp[i-1][j-1]*2
                temp1 = 0
                temp2 = 0

                for k in range(i-1):
                    temp1 += dp[k][j-1]
                for l in range(j-1):
                    temp2 += dp[i-1][l]
                dp[i][j] = temp+temp1+temp2
        print(dp[n][m])
    except:
        break

发表于 2021-01-26 15:57:35 回复(0)

牛客464555119号

C++，经典递归系列

#include <bits/stdc++.h>
using namespace std;
int count(int n, int m){
    if(n==0||m==0)
        return 1;
    return count(n-1,m)+count(n,m-1);
}
int main(){
    int n,m;
    while(cin>>n>>m){
        cout<<count(n,m)<<endl;
    }
    return 0;
}

发表于 2020-08-05 13:58:33 回复(0)

牛客713276588号

输入输出处理简直太**了！

发表于 2020-07-03 00:28:40 回复(0)

Python

^o^201903061215958

思路：动态规划

import sys

def f(n,m):
    if min(n,m)==1:
        return 1 + max(n,m)
    else:
        return f(n,m-1) + f(n-1,m)

for s in sys.stdin:
    s = s.strip().split(" ")
    r = f(int(s[0]), int(s[1]))
    print(r)

编辑于 2020-06-07 22:53:17 回复(0)

C/C++

WZ_Dale

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int m, n;
    while(cin >> m >> n){
        vector<vector<int>> F(m + 1, vector<int>(n + 1, 1));
        for(int i = 1; i < m + 1; ++i){
            for(int j = 1; j < n + 1; ++j){
                F[i][j] = F[i - 1][j] + F[i][j - 1];
            }
        }
        cout << F[m][n] << endl;
    }
    return 0;
}

发表于 2020-06-04 09:49:41 回复(0)

南少201911241210480

#include<iostream>
(720)#include<vector>
using namespace std;
int main()
{
    int dfs(int n,int m);
    int n,m;
    while(cin>>n>>m)//n是列，m是行
    {
       vector<vector<int>>dp(m+1,vector<int>(n+1,1));
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
               dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        cout<<dp[m][n]<<endl;
        //cout<<dfs(n,m)<<endl;
    }
}
int dfs(int n,int m)
{
    if(m==0&&n==0)
        return 1;
    if(m>=0&&n>=0)
    {
        return dfs(n-1,m)+dfs(n,m-1);
    }
    return 0;
}

里面两种解法，一个dp,一个dfs

发表于 2020-04-16 12:08:18 回复(1)

C/C++

牛客227521256号

#include <stdio.h>
(737)#include <string.h>

int n,m,sum,chess[128][128];

void DFS(int x,int y)    //深度优先搜索
{
	chess[x][y] = 1;
	if(x==m && y==n)
	{
		sum++;
		chess[x][y]=0;	
		return;
	}
	if(chess[x+1][y]==0 && x+1<=m)
		DFS(x+1,y);
	if(chess[x][y+1]==0 && y+1<=n)
		DFS(x,y+1);
	chess[x][y]=0;	
}

int main()
{
    while(scanf("%d%d",&n,&m) != EOF)
    {
        DFS(0,0);
        printf("%d\n",sum);
        sum =0;
        memset(chess,0,sizeof(chess));
    }
    return 0;
}

发表于 2020-04-14 23:13:29 回复(0)

牛客344658091号

这题的输入是坑呐~~~

明明说的输入两行，结果确是一行用空格隔开。。。

输出需要说明的是：需要它能够持续跑完所有的测试用例，也就是说需要一次输入一次输出，然后继续接受参数，继续输出，以此类推

发表于 2020-03-30 23:12:50 回复(0)

阿米诺斯

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
            int m=sc.nextInt();
            int n=sc.nextInt();
            int t=m+n;
            int s=m>n?n:m;
            System.out.println(cal(t,s));
        }
    }
    public static int cal(int i,int j){
        if(j==0) return i;
        int a=1,b=1;
        for(int z=0;z<j;z++){
            a*=i-z;
            b*=z+1;
        }
        return a/b;
    }
}

发表于 2020-03-03 17:39:09 回复(0)

C/C++

牛客472374344号


	//可以用递归解决，但是最后的函数出口应该是n = 1或者m = 1的情况

//另外可以用动态规划方法解决（如下）
#include<iostream>
using namespace std;

int main(){
    int n = 0, m = 0;
    while(cin>>n, cin>>m){
        int dp[n+1][m+1];
        for(int i =0;i<n+1;i++){
            for(int j = 0;j<m+1;j++){
                if(i == 0 && j == 0){
                    dp[i][j]= 1;
                }else if(i == 0 && j != 0){
                    dp[i][j] = dp[i][j-1];
                }else if(i != 0 && j == 0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                }
            }
        }
        cout<<dp[n][m]<<endl;
    }
    return 0;
}

发表于 2020-03-02 12:28:32 回复(0)