mXn 그리드의 경로 수

Question

mXn 그리드에서 경로 수를 찾는 방법은 순열을 사용하여 (1,1)부터 도달 할 때까지 한 번에 하나씩 아래쪽, 오른쪽 또는 대각선 방향으로 오른쪽으로 이동합니다. m, n)? 운동이 단지 아래쪽과 오른쪽 인 경우 똑 바른 DP 해결책이 있고 또한 P & C 해결책 (ie m + n-2Cn-1)이다는 것을 나는 알고있다.

Answer 1

이것은 단지 아래쪽과 오른쪽으로 만 움직일 수있는 경로를 계산하는 기존 솔루션 DP 솔루션을 약간 확장해야합니다.

대각선으로 이동할 경우 점에 도달 할 수있는 방법의 수를 세는 것만 변경하면됩니다.

내가 취한 코드는 http://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/입니다. 더 잘 이해하는 데 도움이됩니다.

// Returns count of possible paths to reach cell at row number m and column 
// number n from the topmost leftmost cell (cell at 1, 1) 
int numberOfPaths(int m, int n) 
{ 
    // Create a 2D table to store results of subproblems 
    int count[m][n]; 

    // Count of paths to reach any cell in first column is 1 
    for (int i = 0; i < m; i++) 
     count[i][0] = 1; 

    // Count of paths to reach any cell in first column is 1 
    for (int j = 0; j < n; j++) 
     count[0][j] = 1; 

    // Calculate count of paths for other cells in bottom-up manner using 
    // the recursive solution 
    for (int i = 1; i < m; i++) 
    { 
     for (int j = 1; j < n; j++) 

      //    Rightwards  Downwards  Diagnoally right 
      count[i][j] = count[i-1][j] + count[i][j-1] + count[i-1][j-1]; 

    } 
    return count[m-1][n-1]; 
}