首页 > 试题广场 >

走方格的方案数

[编程题]走方格的方案数
  • 热度指数:120321 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
请计算n*m的棋盘格子(n为横向的格子数,m为竖向的格子数)从棋盘左上角出发沿着边缘线从左上角走到右下角,总共有多少种走法,要求不能走回头路,即:只能往右和往下走,不能往左和往上走。

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

数据范围:



输入描述:

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



输出描述:

输出一行结果

示例1

输入

2 2

输出

6
import java.util.*;

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();
            
            int top = factorial(m+n);
            int behind = factorial(m)*factorial(n);
            System.out.println(top/behind);
        }
    }
    
    public static int factorial(int n)
    {
        int sum = 1;
        for(int i = 1;i<=n;i++)
        {
            sum *= i;
        }
        return sum;
    }
}

发表于 2016-04-08 18:30:57 回复(7)
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.util.*;

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(Fun(n,m));}
    }
    
    public static int Fun(int n,int m){
        if(m==0||n==0){
            return 1;
        }
        
        int result=Fun(m-1,n)+Fun(m,n-1);
        return result;
        
    }
}

发表于 2017-06-03 10:35:42 回复(4)
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)
#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)
#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)
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)
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)
#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)
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)
方法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)
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)
   输入输出处理简直太**了!
发表于 2020-07-03 00:28:40 回复(0)
思路: 动态规划
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)
#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)
#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)
#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)
这题的输入是坑呐~~~
明明说的输入两行,结果确是一行用空格隔开。。。
输出需要说明的是:需要它能够持续跑完所有的测试用例,也就是说需要一次输入一次输出,然后继续接受参数,继续输出,以此类推
发表于 2020-03-30 23:12:50 回复(0)