所以這個問題要求在 MXN 網格中列印從 (1,1) 到 (M,N) 的所有路徑以及相同的路徑總數。
問題陳述
輸入 M 和 N，都是數字。M 和 N 是矩形板上的行數和列數。我們的玩家從棋盤的左上角開始，必須到達右下角。在一次移動中，玩家可以水平（向右）移動 1 步或垂直（向下）移動 1 步或對角線（東南）移動 1 步。
撰寫一個遞回函式，該函式回傳玩家可以穿越棋盤的不同方式的計數。列印回傳的值。
撰寫一個遞回函式，列印所有有效路徑的移動（void 是函式的回傳型別）。
預期輸入/輸出：
Input:
3 3
Output:
VVHH VHVH VHHV VHD VDH HVVH HVHV HVD HHVV HDV DVH DHV DD
13
我的JAVA解決方案
import java.util.*;
public class Main {
static int count = 0;
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
dfs(m, n, 0, 0, new int[m][n], "");
System.out.print("\n" count);
sc.close();
}
static void dfs(int m, int n, int i, int j, int[][] board, String path) {
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == 1) {
return;
}
board[i][j] = 1;
if (i == m - 1 && j == n - 1) {
count ;
System.out.print(path " ");
return; // this line when included does cause problem
}
dfs(m, n, i 1, j, board, path "V");
dfs(m, n, i, j 1, board, path "H");
dfs(m, n, i 1, j 1, board, path "D");
board[i][j] = 0;
}
}
但是當我包含 return 陳述句時，輸出是：
Input:
3 3
Output:
VVHH
1
我不明白為什么當我們已經在董事會的最右下角時有回傳陳述句會有所不同。
任何解釋總是受歡迎的。
uj5u.com熱心網友回復：
問題是這里的這一行：
board[i][j] = 0;
如果您在沒有重置電路板的情況下回傳，您的結果將是不正確的。如果您在if宣告中回傳，就會發生這種情況，因為board[i][j] = 0;不會到達此行。
一個解決方案是將該行添加到if陳述句中：
if (i == m - 1 && j == n - 1) {
count ;
System.out.print(path " ");
board[i][j] = 0;
return;
}
uj5u.com熱心網友回復：
一旦到達單元格，您就不必對其進行標記。因為只要你向右、向下或向右走，你就永遠不會到達同一個牢房。因此，board[][]是不必要的。
static int count = 0;
static void dfs(int m, int n, int i, int j, String path) {
if (i < 0 || i >= m || j < 0 || j >= n) {
return;
}
if (i == m - 1 && j == n - 1) {
count ;
System.out.print(path " ");
return;
}
dfs(m, n, i 1, j, path "V");
dfs(m, n, i, j 1, path "H");
dfs(m, n, i 1, j 1, path "D");
}
public static void main(String[] args) {
dfs(3, 3, 0, 0, "");
System.out.println();
System.out.println(count);
}
輸出：
VVHH VHVH VHHV VHD VDH HVVH HVHV HVD HHVV HDV DVH DHV DD
13
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/371669.html
上一篇：將多維陣列決議為完全指定的端點
下一篇：根據鍵遞回修剪樹（python）