計數/打印路徑 - 從（1,1）到（m，n）

Question

我想計算並打印從矩陣左下角到參數中給定目標的所有可能路徑。你總是從座標（1,1）開始，並且必須向上或向右移動。但是，目標是通過參數傳遞的。例如：CountPath（3，4）

我已經實現了找到正確的路徑數量，但發現我必須從我的目標開始並移動到START，因爲輸入是目標位置。

int CountPath (int row, int column) 
{ 
    if (row == 1 || column == 1) 
     return 1; 
    else 
     return CountPath(row - 1, column) + CountPath(row, column - 1); 
} 

實施例的輸入/輸出： 輸入：3 4 輸出：路徑＃是10

void main() 
{ 
    int m, n; 
    cin >> m >> n; 
    cout << "The # of paths is " << CountPath(m, n) << endl; 
} 

我需要一些澄清上如果我正確地這樣做，或如果有一種方法從（1,1）開始，然後向上和向右移動。印刷應顯示所有可能的路徑，例如：

(1,1)-->(2,1)-->(3,1)-->(3,2)-->(3,3)-->(3,4) 
(1,1)-->(2,1)-->(2,2)-->(3,2)-->(3,3)-->(3,4) 
... 

那麼，有沒有任何遞歸的方式，我可以從（1,1）開始，向上和向右給了這些規則？如果沒有，我怎麼才能按照上面的順序打印它們呢？

Answer 1

原因是您實施CountPath函數的方式。在if語句的內部，您檢查起始座標，因爲它們是最終的，在遞歸調用中，遞減座標而不是遞增座標。這應該工作，你所希望的方式：你實際使用的方式

int CountPath (int row, int column, int maxRow, int maxColumn) 
{ 
    if (row == maxRow || column == maxColumn) 
     return 1; 
    else 
     return CountPath(row + 1, column, maxRow, maxColumn) + CountPath(row, column + 1, maxRow, maxColumn); 
} 

現在，修改一點點，以及：

void main() 
{ 
    int m, n; 
    cin >> m >> n; 
    cout << "The # of paths is " << CountPath(1, 1, m, n) << endl; 
}