計數機器人路徑（python）

Question

我不知道如何開始。

讓我們想象一個5x5的正方形。

機器人從左上角開始安裝在右下角。

我們希望有機器人從左上角的開始廣場到右下角的結束廣場。

在每平方米，機器人有兩個只有一個動作：

它可以去一個方形的權利或 它可能會一平方下來。

編寫一個程序來確定可以做多少種方法？換句話說，從「開始」到「結束」有多少路徑，每個步驟的移動都受到上述限制？

Answer 1

這是通過遞歸樹遍歷表示的。你可以寫一個遞歸的方法來做到這一點，是這樣的：

traverse_moves，走板狀態（機器人，在這種情況下），並返回一個整數

計算下一個動作，你可以做 - 總數從0到2。如果爲0，則返回整數1。如果是1或2，則爲每個有效移動創建棋盤狀態，並以您創建的狀態調用此方法，將所有調用的返回值相加並返回所得的總和。

例如對於2x2板，創建機器人位於左上角的狀態。這個狀態有兩種可能的動作，所以它會自動調用機器人左下角和機器人右上角。這些州中的每一個都有一個可能的舉措，並會用右下角的機器人自行調用。遍歷樹的這兩個「葉子」將返回1，並且這些1將被返回並傳播，並將遞歸歸結爲給出2作爲正確答案。

Caller 
    | 2 
    TL calls itself with BL and TR 
/1 \ 1 
BL TR call themselves with BR, their only valid move 
| 1 | 1 
BR BR return 1s each for being leaf nodes, the 1s are returned and summed 

編輯：僞

int traverseMoves(BoardState state) 
{ 

    List<BoardState> nextMoves = possibleMovesFrom(state); 
    if (nextMoves.Length == 0) 
    { 
     return 1; 
    } 

    int returnValue = 0; 
    foreach (BoardState move in nextMoves) 
    { 
     returnValue += traverseMoves(move); 
    } 
    return returnValue; 
}