我知道這里還有很多其他迷宮求解器。雖然我想有自己的方法，但我認(rèn)為我的問(wèn)題與其他人有點(diǎn)不同。到目前為止，這就是我已經(jīng)開(kāi)始的事情，希望我能實(shí)現(xiàn)我現(xiàn)在的想法。 private static int getPossiblePaths(File f) throws IOException { int counts = 0; // hope to return all possible paths // read input file then put it on list string List<String> lines = Files.lines(f.toPath()).collect(Collectors.toList()); // get the row and column (dimensions) String[] dimensions = lines.get(0).split(","); //initalize sub matrix of the maze dimensions and ignoring the top and bottom walls int[][] mat = new int[Integer.valueOf(dimensions[0]) - 2 ][Integer.valueOf(dimensions[1]) - 2]; //for each line in the maze excluding the boundaries (top and bottom) for( int i = 2 ; i < lines.size() - 1 ; i++) { String currLine = lines.get(i); int j = 0; for(char c : currLine.toCharArray()) { mat[i-2][j] = (c=='*' ? 'w' : c=='A' ? 'a' : c=='B' ? 'b' : 's'); // some conditional statements here } }// or maybe some conditional statements here outside of the loop return counts;}文本文件中的迷宮看起來(lái)像這樣。請(qǐng)注意，A 可以在任何地方并且與 B 相同。唯一允許的移動(dòng)是向右和向下。5,5******A ** ** B******上述迷宮的預(yù)期輸出是 6（從 A 到 B 的可能路徑）。編輯：文本文件中的迷宮也可能是這樣的：8,5********* A ** B** *********因此，使用我當(dāng)前的代碼，它獲取尺寸（第一行）并刪除迷宮的頂部和底部部分（邊界）。所以目前mat數(shù)組中只存儲(chǔ)了 3 行字符。以及文本文件中每個(gè)字符的一些編碼（#=w(wall), A=a(start), B=b(end), else s(space)）我想在 foreach 內(nèi)部有一些條件語(yǔ)句，以便可能將每個(gè)字符存儲(chǔ)在 ArrayList 中。盡管我不確定這種方法是否會(huì)讓我的生活變得更加困難。如果你們有任何建議、技巧、建議或其他更簡(jiǎn)單的方法，我們將不勝感激！謝謝
2 回答
蝴蝶刀刀
TA貢獻(xiàn)1801條經(jīng)驗(yàn) 獲得超8個(gè)贊
創(chuàng)造的想法mat很好。我不會(huì)費(fèi)心去去掉第一行和最后一行，因?yàn)槭聦?shí)上，當(dāng)你保留它們時(shí)，使用它們會(huì)更容易。這樣，i-1當(dāng)您位于非墻壁位置時(shí)，行引用就不會(huì)超出范圍。
我也不會(huì)像w在那里存儲(chǔ)字符，而是存儲(chǔ)特定的數(shù)字，例如 -1 表示墻壁，0 表示免費(fèi)。還為“A”和“B”存儲(chǔ) 0。當(dāng)遇到這兩個(gè)字母時(shí)，您可以將它們的坐標(biāo)存儲(chǔ)在特定變量中（例如rowA, colA, rowB, colB）。您可能需要檢查 B 是否位于 A 的右下方，否則肯定無(wú)法從 A 到達(dá) B。
所以我將定義mat如下（請(qǐng)注意，我顛倒了尺寸，因?yàn)槟牡诙€(gè)示例表明輸入的第一行按該順序排列它們）：
int[][] mat = new int[Integer.valueOf(dimensions[1])]
[Integer.valueOf(dimensions[0])];
int colA = mat[0].length;
int rowA = 0;
int colB = colA;
int rowB = 0;
for (int i = 0; i < mat.length; i++) {
String currLine = lines.get(i+1);
int j = 0;
for (char c : currLine.toCharArray()) {
mat[i][j] = c == '*' ? -1 : 0;
if (c == 'B') {
if (colA > j) return 0; // B unreachable from A
rowB = i;
colB = j;
} else if (c == 'A') {
if (colB < j) return 0; // B unreachable from A
rowA = i;
colA = j;
}
j++;
}
}
通過(guò)此設(shè)置，您可以重復(fù)mat存儲(chǔ)從 A 到當(dāng)前位置的路徑數(shù)。值 0 atA應(yīng)設(shè)置為 1（從 A 到 A 僅有一條路徑），然后將上方和左側(cè)單元格中的值相加，確保 -1 被視為 0。
mat[rowA][colA] = 1;
for (int i = rowA; i <= rowB; i++) {
for (int j = colA; j <= colB; j++) {
if (mat[i][j] == 0) { // not a wall?
// count the number of paths that come from above,
// plus the number of paths that come from the left
mat[i][j] = Math.max(0, mat[i-1][j]) + Math.max(0, mat[i][j-1]);
}
}
}
return mat[rowB][colB]; // now this has the number of paths we are looking for
雖然遞歸方法也可以工作，但我建議使用上述動(dòng)態(tài)編程方法，因?yàn)檫@樣可以避免多次重新計(jì)算某個(gè)單元的計(jì)數(shù)（當(dāng)通過(guò)不同的 DFS 路徑到達(dá)那里時(shí)）。該解決方案具有線性時(shí)間復(fù)雜度。
繁華開(kāi)滿天機(jī)
TA貢獻(xiàn)1816條經(jīng)驗(yàn) 獲得超4個(gè)贊
我建議使用 2 次調(diào)用進(jìn)行簡(jiǎn)單的遞歸：向下和向右。
這是代碼：
import java.io.File;
import java.io.IOException;
import java.lang.invoke.MethodHandles;
import java.net.URISyntaxException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.List;
import java.util.stream.Collectors;
public class JavaMazeInsideOfWallsAndGetAllPossiblePaths {
public static void main(String[] args) throws IOException, URISyntaxException {
Path mazePath = Paths.get( MethodHandles.lookup().lookupClass().getClassLoader()
.getResource("maze.txt").toURI());
File mazeFile = mazePath.toFile();
System.out.println(getPossiblePaths(mazeFile));
}
private static int getPossiblePaths(File f) throws IOException {
// read input file then put it on list string
List<String> lines = Files.lines(f.toPath()).collect(Collectors.toList());
// get the row and column (dimensions)
String[] dimensions = lines.get(0).split(",");
//initalize sub matrix of the maze dimensions and ignoring the top and bottom walls
int[][] mat = new int[Integer.valueOf(dimensions[0]) - 2 ][Integer.valueOf(dimensions[1]) - 2];
int fromRow = -1, fromCol = -1, toRow = -1, toCol = -1;
for( int i = 2 ; i < lines.size() - 1 ; i++) {
String currLine = lines.get(i);
int j = 0;
for(char c : currLine.toCharArray()) {
switch(c) {
case '*':
continue; // for loop
case 'A':
mat[i-2][j] = 0;
fromRow = i-2;
fromCol = j;
break;
case 'B':
mat[i-2][j] = 2;
toRow = i-2;
toCol = j;
break;
default:
mat[i-2][j] = 1;
}
j++;
}
}
return getPossiblePathsRecursive(mat, fromRow, fromCol, toRow, toCol);
}
private static int getPossiblePathsRecursive(int[][] mat, int i, int j, int rows, int columns) throws IOException {
if(i > rows || j > columns) {
return 0;
}
if(mat[i][j] == 2) {
return 1;
}
return getPossiblePathsRecursive(mat, i+1, j, rows, columns) +
getPossiblePathsRecursive(mat, i, j + 1, rows, columns);
}
}
注意： 1. 跳過(guò)驗(yàn)證步驟（假設(shè)輸入數(shù)據(jù)采用有效格式） 2. 忽略墻壁（假設(shè)始終有 4 堵墻 - 第一行、最后一行、第一列、最后一列。這些墻假設(shè)表示為“*”）
添加回答
舉報(bào)
0/150
提交
取消