二維迷宮的遞歸算法？

（這不是重複的）我們在所有4邊都有一個由X包圍的2D迷宮，並且也有內部塊。
迷宮中的所有這些字符都存儲在二維數組中。程序必須找到從開始'S'到目標'G'的路徑。爲此，一個名爲'solve（int row，int col）的布爾方法被使用並且用'S'的行和列索引進行初始化。該算法必須是遞歸的。它應該返回true，如果它能夠找到'G'的路徑並且其他方式是錯誤的。以下是我試圖解決這個顯示「部分正確結果」的問題。二維迷宮的遞歸算法？

public boolean solve(int row, int col) { 
    char right = this.theMaze[row][col + 1]; 
    char left = this.theMaze[row][col - 1]; 
    char up = this.theMaze[row - 1][col]; 
    char down = this.theMaze[row + 1][col]; 
    if (right == 'G' || left == 'G' || up == 'G' || down == 'G') { 
    return true; 
    } 
    System.out.println("position=>"+"("+row + ":" + col+")"); 
    if (right == ' ') { 
    return solve(row,col+1); 
    } 
    if (down == ' ') { 
    return solve(row+1,col); 
    } 
    if (left == ' ') { 
    return solve(row,col-1); 
    } 
    if (up == ' ') { 
    return solve(row-1,col); 
    } 
    return false; 
}

這裏是它解決了輸出：

0 1 2 3 4 5 6 7 8 9 10 
0 X X X X X X X X X X X 
1 X X S X X X X X X X 
2 X X X X X X X X X 
3 X X X X X X X X X 
4 X X X X X X X X X 
5 X X X X X X X X X 
6 X X X X X X X X X 
7 X X X X X X X G X X 
8 X X    X X 
9 X X X X X X X X X X X 

position=>(1:2) 
position=>(2:2) 
position=>(3:2) 
position=>(4:2) 
position=>(5:2) 
position=>(6:2) 
position=>(7:2) 
position=>(8:2) 
position=>(8:3) 
position=>(8:4) 
position=>(8:5) 
position=>(8:6) 
position=>(8:7) 
true

但是，當我把 'G' 一步向上（在6,8）。它顯示堆棧溢出錯誤。原因是因爲遞歸發生在這個狀態的2個點之間（不知怎的，就像間接遞歸一樣）。

我該如何解決這個問題。無論如何要讓程序向上移動而不是向下移動？改變條件語句的位置不會工作。並且認爲一個有多條路徑但只有一條導致'G'的位置。如何回到初始位置並嘗試另一條路徑？提前致謝。

更新：

Here is a Github Repo link to the complete solution of this problem by me.

來源

2013-11-25 Prashant Ghimire

在你目前的代碼中有你回到了false不看其他連接位置的可能性。

在退出if條件之前，您應該查看其他可能性。
此外，你應該檢查位置是否已被訪問，以避免無限遞歸。

你的代碼更改爲：

bool solved = false; 
visited[row][col] = true; 

if (right == ' ' && !visited[row][col+1]) { 
    solved = solve(row,col+1); 
} 
if (down == ' ' && !solved && !visited[row+1][col]) { 
    solved = solve(row+1,col); 
} 
if (left == ' ' && !solved && !visited[row][col-1]) { 
    solved = solve(row,col-1); 
} 
if (up == ' ' && !solved !visited[row-1][col]) { 
    solved = solve(row-1,col); 
} 
return solved;

來源

2013-11-25 08:18:06

我會嘗試，看看它是否工作。 –

絕對，它現在工作！ –

你可以在你通過加強空間的替代符號填寫已經使你的程序就知道它在那裏了。

來源

2013-11-25 08:19:48

對我來說聽起來不錯，imma試試。謝謝！ –

您可以使用DFS或BFS。 DFS是最簡單的一個。您只需進行遞歸，在所有4/8方向上導航並將該地點（X，Y）標記爲已訪問。如果它是你的命運'G'，則返回true否則繼續。

提示：

不要使用相同的矩陣來讀取地圖和參觀紀念它，KISS
你必須不斷地檢查，如果你已經發現G.你可以回報使這始終爲FALSE或TRUE，或者您可以使用全局變量。

如果你有實現的麻煩就嘗試谷歌的一些源代碼，關於這個問題： http://en.wikipedia.org/wiki/Flood_fill

http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

來源

2013-11-25 10:19:35

下面是一個僞代碼爲您解決了迷宮，也追溯解決方案： -

boolean Solve(int x,int y) { 

    if(isTarget(x,y)) 
     return(true) 

    if(valid(x+1,y)&&Map[x+1][y]==' ') { 
     Map[x][y] = 'D' 
     if(Solve(x+1,y)) 
     return(true) 
     Map[x][y] = ' ' 
    } 
    if(valid(x-1,y)&&Map[x-1][y]==' ') { 
     Map[x][y] = 'U' 
     if(Solve(x-1,y)) 
     return(true) 
     Map[x][y] = ' ' 
    } 
    if(valid(x,y+1)&&Map[x][y+1]==' ') { 
     Map[x][y] = 'R' 
     if(Solve(x,y+1)) 
     return(true) 
     Map[x][y] = ' ' 
    } 
    if(valid(x,y-1)&&Map[x][y-1]==' ') { 
     Map[x][y] = 'L' 
     if(Solve(x,y-1)) 
     return(true) 
     Map[x][y] = ' ' 
    } 

    return(false); 
}

來源

2013-11-25 10:45:34

櫃面您正在尋找完整的解決方案，我已經上傳它在我的Github Repository。

來源

2014-10-20 18:19:02

本文Solving a 2D Maze通過啓發，遞歸解決方案

const CORRIDOR = 0; 
 
const WALL = 1; 
 
const EXIT = 2; 
 

 
// board - 2D array 
 
// start - [row, column] location of start point 
 

 
function findPath(board, start) { 
 
    let seenPath = new Set(); 
 

 
    findPathRecur(board, start, seenPath) 
 

 
    return Array.from(seenPath); 
 
} 
 

 
function findPathRecur(board, point, seenPath) { 
 
    let row = point[0], 
 
    column = point[1]; 
 
    
 
    // Base Case 
 
    if (!isValidPathPoint(board, point, seenPath)) { 
 
    return false; 
 
    } 
 

 
    if (board[row][column] === EXIT) { 
 
    seenPath.add(point.toString()); 
 
    return true; 
 
    } 
 
// console.log("Curr -", point, ", Seen -", Array.from(seenPath)); 
 

 
\t seenPath.add(point.toString()); 
 

 
    let leftColumn = [row, column - 1], 
 
    rightColumn = [row, column + 1], 
 
    topRow = [row - 1, column], 
 
    bottomRow = [row + 1, column]; 
 

 
    if (findPathRecur(board, leftColumn, seenPath)) { 
 
    return true; 
 
    } 
 
    if (findPathRecur(board, rightColumn, seenPath)) { 
 
    return true; 
 
    } 
 
    if (findPathRecur(board, topRow, seenPath)) { 
 
    return true; 
 
    } 
 
    if (findPathRecur(board, bottomRow, seenPath)) { 
 
    return true; 
 
    } 
 

 
    seenPath.delete(point.toString()); 
 

 
    return false; 
 
} 
 

 
// Check if the point is on valid path 
 
function isValidPathPoint(board, point, seenPath) { 
 
    let row = point[0]; 
 
    let column = point[1]; 
 

 
    // Check if point exists 
 
    if (board[row] != null && board[row][column] != null) { 
 

 
    // To avoid cycle 
 
    if (!seenPath.has(point.toString())) { 
 
     // Not a Wall 
 
     if (board[row][column] !== WALL) { 
 
     return true; 
 
     } 
 
    } 
 
    } 
 
    return false; 
 
} 
 

 
// Test Program 
 
let maze = [ 
 
    [1, 1, 1], 
 
    [0, 0, 1], 
 
    [1, 2, 1] 
 
]; 
 

 
let testStart = [ 
 
\t [1,0], 
 
    [1,1], 
 
    [2,1], 
 
    [0,0], 
 
    [5,5] 
 
]; 
 

 
testStart.forEach(function(start, i) { 
 
\t console.log("Test Case:",i); 
 
    console.log("\tStart -", start, "Path -", findPath(maze, start)); 
 
})

來源

2017-05-11 15:53:00 Rohit

二維迷宮的遞歸算法？

回答

相關問題