您將獲得一個 NxN (2 <= N <= 50) 個點的正方形，但其中一些點可以是 H（被阻止），這意味著您無法繼續使用它們。您還將獲得 T (1 <= T <= 3)，這是您允許進行的最大轉彎次數。你從圖表的左上角開始，你必須把它放到圖表的右下角。您只能向下或向右移動。以下是可能的圖形的三個示例。
N = 3, T = 3
...
.H.
...
Output: 2
N = 4, T = 3
...H
.H..
....
H...
Output: 6
N = 3, T = 2
.HH
HHH
HH.
Output: 0
D 表示向下移動，R 表示向右移動。對于第一種，兩種方式是 DDRR 和 RRDD。對于第二種，六種方式是DDRDRR、DDRRDR、DDRRRD、RRDDDR、RRDDRD和RRDRDD。對于最后一個，沒有辦法讓它到右下角。
我曾想過的一件事是使用 DFS 可能可以解決此問題，但我不知道如何針對此問題實施它。任何幫助都會非常有幫助。
我已經嘗試過這種遞回方法，但我很確定我完全走錯了路。
public static void step(char[][] graph, int[] pos, int turns, int max)
{
if(turns > max) return;
else if(pos[0] == graph.length-1 && pos[1]==graph.length-1)
{
count ;
return;
}
else if(pos[0] == graph.length && graph[pos[0] 1][pos[1]] == 'H') return;
else if(pos[1] == graph.length && graph[pos[0]][pos[1] 1] == 'H') return;
else if(graph[pos[0] 1][pos[1]] == 'H' && graph[pos[0]][pos[1] 1] == 'H') return;
else {
step(graph, new int[]{pos[0] 1, pos[1]}, turns 1, max);
step(graph, new int[]{pos[0], pos[1] 1}, turns 1, max);
}
}
uj5u.com熱心網友回復：
我在你的函式中發現了一些錯誤：
檢查您是否越界的條件不需要檢查是否有 H ：越界意味著什么都沒有，所以pos[0] == graph.length應該足以停止。
檢查是否有 H 擋路的條件也是錯誤的：要停止，您需要在您的右下方都有一個 H。這意味著你仍然會探索一些通過 H 的路徑。如果您目前在 H 上，您可以做的是停止：if(graph[pos[0]][pos[1]] == 'H')
遞回呼叫總是增加圈數。轉彎是您允許進行的步數，還是您可以改變方向的次數？如果是后者，則需要在呼叫中傳遞當前方向，只有改變方向才會增加。最初的呼叫有點棘手，因為您實際上沒有第一步的方向。
全域觀察是您似乎混合了邏輯“與”運算子 (&&)。也許我錯了，但快速回顧可以幫助你，因為“或”在那里似乎更合乎邏輯。
uj5u.com熱心網友回復：
是的。假設轉數是你改變方向的次數，你需要跟蹤方向，只有turns在方向改變時才增加：
public static void step(char[][] graph, int[] pos, int turns, int max,
char dir)
{
if(turns > max) return;
else if(pos[0] == graph.length-1 && pos[1]==graph.length-1)
{
count ;
return;
}
if(pos[0] < graph.length && pos[1] < graph.length
&& graph[pos[0]][pos[1]] != 'H') {
step(graph, new int[]{pos[0] 1, pos[1]}, dir != 'R' ? turns : turns 1, max, 'D');
step(graph, new int[]{pos[0], pos[1] 1}, dir != 'D' ? turns : turns 1, max, 'R');
}
}
初始呼叫將傳遞既不是'D'也不是 的任何字符'R'：
step(graph, new int[]{0, 0}, 0, t, '?');
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/391645.html