Найти номер уникального пути в матрице

Question

Учитывая матрицу MXN с вашей начальной позицией в верхней левой ячейке, найдите количество возможных уникальных путей для достижения нижней правой ячейки матрицы из начальной позиции.
Возможные перемещения могут быть либо вниз, либо вправо вв любой момент времени.

Для ввода 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

Если матрица nxm, то число уникальных путей равно (n + m-2)! / ((N-1)! (M-1)!).Вы можете просто закодировать эту формулу.

См. Комбинация в Википедии.

Answer 2

Вы можете посмотреть на это так:

Когда вы находитесь в верхнем левом углу и двигаетесь вниз, вы получаете новую матрицу с на 1 строкой меньше и таким же количеством столбцов.

Когда вы находитесь в верхнем левом углу и двигаетесь на 1 правую часть, а затем вниз, вы получаете новую матрицу с 1 строкой меньше и на 1 столбец меньше.

Когда вы находитесь в левом верхнем углу и двигаетесь на 2 правой части, а затемвниз, вы получите новую матрицу с 1 строкой меньше и 2 столбцами меньше.

и т. д.

Таким образом, чтобы вычислить результат для матрицы (R, C), вы можете вычислить еекак сумма результата из ряда меньших матриц.Как:

count(R, C) = count(R-1, C-0) + count(R-1, C-1) + count(R-1, C-2) + ... + count(R-1, 1)

Это может быть обработано рекурсией.Что-то вроде:

#include <stdio.h>

int count(int r, int c)
{
  if (r == 1) return 1;
  if (c == 1) return 1;
  int sum = 0;
  for (int i=0; i < c; ++i)
  {
      sum += count(r-1, c-i);
  }

  return sum;
}

int main()
{
  int r=5, c=11;
  int res=count(r,c);
  printf("Result: %d\n", res);
}

Answer 3

Ваша программа слишком сложна. Сначала вы должны изучить способ построения путей, чтобы выиграть время.

Когда в данной точке 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