public static int printStepsToReachBottom(int rows, int columns, String[] array) {
if (rows == 1) {
array[0] = ""/span>;
for (int i = 0; i < columns - 1; i ) {
array[0] = "H"/span>;
}
return 1;
}
if (columns == 1) {
array[0] = ""/span>;
for (int i = 0; i < rows - 1; i ) {
array[0] = "V"/span>;
}
return 1;
}
String[] temporary = new String[1000] 。
int k = 0;
int firstTypeMove = printStepsToReachBottom（rows - 1, columns, array）。
for (int i = 0; i < firstTypeMove; i ) {
temporary[k] = array[i] "V"/span>;
k ;
}
int secondTypeMove = printStepsToReachBottom(rows, columns - 1, array) 。
for (int i = 0; i < secondTypeMove; i ) {
temporary[k] = array[i] "H"/span>;
k ;
}
for (int i = 0; i< secondTypeMove firstTypeMove; i ) {
array[i] = temporary[i];
}
return secondTypeMove firstTypeMove;
}
public static void main（String[] args） {
String[] array = new String[1000] 。
int outputSize = printStepsToReachBottom(2, 2, array) 。
for (int i = 0; i < outputSize; i ) {
System.out.println(array[i])。
}
我搞不清楚這個代碼段是如何作業的。我不明白其中的邏輯。它列印出到達m*n矩陣底部的所有可能路徑 它列印了2x2矩陣的 "HV "和 "VH"。請幫助我。
uj5u.com熱心網友回復：
你可以把代碼分解成三個部分；
if (rows == 1) {
array[0] = ""/span>;
for (int i = 0; i < columns - 1; i ) {
array[0] = "H"/span>;
}
return 1;
}
if (columns == 1) {
array[0] = ""/span>;
for (int i = 0; i < rows - 1; i ) {
array[0] = "V"/span>;
}
return 1;
這部分是遞回的結束情況。它說沒有更多的行或列了，并回傳一個大小為1的陣列，其中包含H（或H的）或V（或V的）
。String[] temporary = new String[1000] 。
int k = 0;
int firstTypeMove = printStepsToReachBottom（rows - 1, columns, array）。
for (int i = 0; i < firstTypeMove; i ) {
temporary[k] = array[i] "V"/span>;
k ;
}
int secondTypeMove = printStepsToReachBottom(rows, columns - 1, array) 。
for (int i = 0; i < secondTypeMove; i ) {
temporary[k] = array[i] "H"/span>;
k ;
}
第二部分通過H和V兩個方向執行遞回，對于任何給定的步驟，這在堆疊中又增加了兩個遞回呼叫（雖然在執行程序中，它執行的是深度優先搜索，而不是廣度優先搜索，但這樣的想法更容易掌握）
。
int secondTypeMove = printStepsToReachBottom（rows, columns - 1, array）。)
for (int i = 0; i < secondTypeMove; i ) {
temporary[k] = array[i] "H"/span>;
k ;
}
for (int i = 0; i< secondTypeMove firstTypeMove; i ) {
array[i] = temporary[i];
}
return secondTypeMove firstTypeMove;
最后一部分將H和V方向的輸出收集到全域陣列中，并將輸出的數量回傳到上層堆疊。
uj5u.com熱心網友回復：
下面是一個更簡單的遞回深度優先搜索，它可以做同樣的事情：
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main（String[] args） {
dfsPrintAllPathesTopToBottom(3,3) 。
}
//執行dfs來映射行x列矩陣上的所有可能路徑。
//from top left to bottom right by moving right (R) or down (R)
public static void dfsPrintAllPathesTopToBottom(int rows, int columns){
List<String> path = new ArrayList<>（）。
dfsPrintAllPathesTopToBottom(0, 0, rows,columns,path)。
}
public static void dfsPrintAllPathesTopToBottom(int row, int col, int rows, int columns, List< String> path ){
if(row == rows -1 && col == columns -1){//bottom left reached。
System.out.println(path)。
return。
}
//向右移動。
int newCol = col 1;
if(newCol < columns ){
List<String>newPath = new ArrayList<>（path）。
newPath.add("R"); /or newPath.add("H")
dfsPrintAllPathesTopToBottom（row, newCol, rows, columns, newPath）。
}
//向下移動。
int newRow = row 1;
if(newRow < rows ){
List<String>newPath = new ArrayList<>（path）。
newPath.add("D"/span>); /or newPath.add("V")
dfsPrintAllPathesTopToBottom(newRow, col, rows, columns, new ArrayList<>（newPath）)。
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/319328.html
標籤：
下一篇：堆疊中的方法呼叫如何被執行-遞回