我要招人

去企业版

首页 > 试题广场 >

走方格的方案数

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

热度指数：122096 时间限制：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

输出

算法知识视频讲解

猪猪侠的飞天梦

利用动态规划来做最简单，时间复杂度最低

#include <stdio.h>
inline int func(int m, int n) {
    int map[100][100] = {0};
    for (int i = 0; i < n; i++) map[0][i] = 1;
    for (int i = 1; i < m; i++) map[i][0] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            map[i][j] = map[i - 1][j] + map[i][j - 1];
        }
    }
    return map[m - 1][n - 1];
}
int main() {
    int m = 0, n = 0;
    scanf("%d %d", &m, &n);
    printf("%d", func(++m, ++n));
    return 0;
}

编辑于 2023-12-16 20:24:58 回复(0)

彭洋a

#include <stdio.h>

int sum(int m,int n)

{

if(m==1&&n==1)

{

return 2;

}

else if(m==1||n==1)

{

if(m == 1)

{

return n+1;

}

else

{

return m+1;

}

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

}

int main() {

int a, b;

while (scanf("%d %d", &a, &b) != EOF) {

int ret = sum(a,b);

printf("%d\n",ret);

}

return 0;

}

发表于 2023-10-13 23:45:42 回复(0)

Jackn

#include <stdio.h>

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

int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    printf("%d\n",f(n,m));
    return 0;
}
递归方法

发表于 2023-03-28 20:02:19 回复(0)

好久不见，最近好吗

#include <stdio.h>
#include <stdlib.h>
int ** malloc_planar_array_int(int row,int col)
{
int **p = NULL;
int i = 0;
p = (int**)malloc(sizeof(int *)*(row));
if(!p)
{
return NULL;
}
for(i = 0;i<row;i++)
{
p[i] = malloc(sizeof(int)*(col));
if(!p[i])
{
return NULL;
}
}
return p;
}

void free_planar_array_int(int **p,int row)
{
int i = 0;
if(!p) return;
for(i = 0;i<row;i++)
{
if(p[i])
{
free(p[i]);
p[i] = NULL;
}
}
free(p);
p = NULL;
}
int main()
{
int i,j,n,m;
int **dp = NULL;
while(scanf("%d%d",&n,&m)!=EOF)
{
dp = malloc_planar_array_int(n+1,m+1);
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(i==0||j==0)
dp[i][j]=1;
else
dp[i][j]=dp[i][j-1]+dp[i-1][j];
}
}
printf("%d\n",dp[n][m]);
free_planar_array_int(dp,n+1);
}
return 0;
}

发表于 2022-06-19 17:05:20 回复(0)

已注销

#include <stdio.h>
#define    N    100
int main()
{
    int dp[N][N],i,j,n,m;
    scanf("%d%d",&n,&m);
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=m;j++)
        {
            if(i==0||j==0)
                dp[i][j]=1;
            else
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
        }
    }
    printf("%d\n",dp[n][m]);
    return 0;
}

发表于 2022-04-26 08:59:26 回复(0)

海饼干666

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    int tmp = 0,cnt = 0;
    int rc[2] = {0,0};
    
    while(scanf("%d",&tmp) != EOF)
    {
        if(tmp != ' ' && tmp != '\n')
        {
            rc[cnt++] = tmp+1;
        }
        if(cnt == 2)
        {
            int **map = (int *)malloc(rc[0] * sizeof(int*));
            for(int i = 0; i < rc[0]; i++)
            {
                map[i] = (int *)malloc(rc[1] * sizeof(int));
                memset(map[i],0,rc[1]);
            }
            
            for(int j = 0; j < rc[1]; j++) map[0][j] = 1;
            for(int i = 0; i < rc[0]; i++) map[i][0] = 1;
            for(int i = 1; i < rc[0]; i++)
            {
                for(int j =1; j < rc[1]; j++)
                {
                    map[i][j] = map[i][j-1] + map[i-1][j];
                }
            }
            
            printf("%d\n",map[rc[0]-1][rc[1]-1]);
            cnt = 0;
        }
    }
    
    return 0;
}

发表于 2021-09-03 15:31:07 回复(0)

牛客415544593号

#include<stdio.h>

int path(a,b)
{
    if(a==0 || b==0)
        return 1;
    else
        return path(a-1,b)+path(a,b-1);
}

int main()
{
    int num1,num2;
    while(scanf("%d %d",&num1,&num2)!=EOF)
    {
        printf("%d\n",path(num1,num2));
    }
    return 0;
}

发表于 2021-08-17 23:18:01 回复(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)