c - 查找矩阵中唯一路径的数量

Question

给定一个 M X N 矩阵，初始位置位于左上角单元格，请找出从初始位置到达矩阵右下角单元格的可能唯一路径的数量。
在任何时间点，可能的走势都可以是向下或向右。

对于M=5，N=11的输入。正确的输出应该是1001。
不同IDE的输出是不同的。

 #include<stdio.h>

 int div(int tot,int j,int n,int m)
 {
      int i;
      int fn=1;
      int fd=1;
      int f=1;
      int p;
      for(i=tot;i>=j;i--)
      {
              fn=fn*i;
      }
      for(i=n;i>=1;i--)
      {
              fd=fd*i;
      }
      p=fn/fd;

      for(i=j-1;i>=m+1;i--)
              f=f*i;
              p=p*f;

              return p;


}



int main()
{
              int M,N;
              int unqPath;
              int i,T;
              int j,path;
              int m,n;
              int flag=0;
              scanf("%d",&T);

              for(i=0;i<T;i++)
              {
                      scanf("%d",&M);
                      scanf("%d",&N);

                      if(M>=N)
    {
        path=1;
        for(j=(M-1)+(N-1);j>(M-1);j--)
        {

            path=path*j;
            if(path<=0)
            {

                unqPath=div(((M-1)+(N-1)),j+1,N-1,M-1);
                flag=1;
                printf("\n\n%d",unqPath);
                break;
            }

        }



        if(flag==0)
        {

            n=1;
            for(j=(N-1);j>=1;j--)
            {


                n=n*j;
            }

            unqPath=path/n;
            printf("%d",unqPath);
        }
    }
    else
    {
        path=1;
        for(j=(M-1)+(N-1);j>(N-1);j--)
        {


            path=path*j;
            if(path<=0)
            {
                unqPath=div((M-1)+(N-1),j+1,M-1,N-1);
                flag=1;
                printf("%d",unqPath);
                break;
            }
        }
        if(flag==0)
        {


            m=1;
            for(j=(M-1);j>=1;j--)
            {

                m=m*j;
            }
            unqPath=path/m;

            printf("\n%d",unqPath);
        }
    }
}

    return 0;
}

Answer 1

你的程序太复杂了。您应该首先研究路径的构建方式以获得时间。

当在给定点 x,y 时，您可以向下或向右移动。所以从该点开始的路径数就是向下或向右的路径数之和。
特殊情况是当该点位于边界上时，那里只有一条路径。

因此，您将得到以下带有计算递归实现的代码:

#include <stdio.h>

// cells are numbered (1..xmax, 1..ymax)
// x an y are position of points
// xmax and ymax are the rectangle size
int nbrpaths(int x, int y, int xmax, int ymax)
{
  if(x==xmax || y==ymax) return 1; // On a south or east border ->
                                   // only one solution: go straight right or down
  return nbrpaths(x+1,y,xmax,ymax)   // go right and find a path 
        + nbrpaths(x,y+1,xmax,ymax); // go down and find a path
}

int main()
{
  int xmax=5, ymax=11, x=1, y=1;
  int nbr=nbrpaths(x,y,xmax,ymax);
  printf("number of paths: %d\n",nbr);
}
// prints: number of paths: 1001