找到從迷宮（廣度優先搜索）

Question

晚安的最短路徑。我有一個以矩陣形式表示的迷宮。有一個起點和一個終點。我寫了一個函數，將所有可以訪問的單元格添加到數組中。該函數還會刪除所有沒有後代（死鎖）的單元格。但該功能不會刪除導致死衚衕的單元格。請幫助完成該功能。

//maze 
matrix = [ 
    [0, 1, 0, 1, 0], 
    [0, 0, 1, 0, 0], 
    [0, 0, 1, 1, 0], 
    [0, 0, 0, 0, 0], 
    [0, 1, 0, 1, 0] 
]; 

var start = [4, 0]; 
var end = [3, 4]; 

function findWay(position, end) { 

    var queue = []; 

//an array that contains the cells that have already visited 
    var visited = []; 

//An array that contains cells that can not be entered for this position 
    var invalidCells = []; 

//mark the current cell with a unit so as not to visit it anymore.  
    matrix[position[0]][position[1]] = 1; 

//add the current position to the queue 
    queue.push(position); 

//until the queue is empty  
    while (queue.length > 0) { 

//get the first element of the queue  
    var pos = queue.shift(); 


    //we clear the array, because for each new position we will have our own array  
    invalidCells.length = 0; 


    //an array of motion directions 
    var direction = [ 
     [pos[0] + 1, pos[1]], 
     [pos[0], pos[1] + 1], 
     [pos[0] - 1, pos[1]], 
     [pos[0], pos[1] - 1] 
    ];      

    for (var i = 0; i < direction.length; i++) { 

//do a check for each direction 
//if at least one cell does at least one of the conditions, the cell is 
    placed in an array of invalid cells 
//then run a new iteration of the loop 

     if (direction[i][0] < 0 || direction[i][0] >= matrix[0].length || direction[i][1] < 0 || direction[i][1] >= matrix[0].length || matrix[direction[i][0]][direction[i][1]] != 0) { 

     invalidCells.push(direction[i]); 
     continue; 
     } 

    //If this direction turned out to be an end cell 
    //return the array of visited cells 
     if (direction[i][0] == end[0] && direction[i][1] == end[1]) return visited; 

    //if none of the conditions are met, mark this direction with one and add it to the end of the queue 
     matrix[direction[i][0]][direction[i][1]] = 1; 
     queue.push(direction[i]); 
    } 

    //add the current position to the array of visited cells 
    visited.push(pos); 

    //If no iteration of the loop returns anything, then this cell is a dead end 
    if (invalidCells.length == 4) { 

    //remove the deadlock from the array 
     visited.pop(); 
    } 
    } 
} 

findWay(start, end); 

Answer 1

似乎沒有必要保留的visited和invalidCells跟蹤：

• visited包含所有訪問過的小區（在各個方向）。雖然你嘗試，一旦你達到一個死衚衕從中去除細胞，沒有原路返回，並從中刪除其他細胞，從而導致這個死衚衕沒有簡單的方法，並沒有參與其他路徑，可能仍然是成功的。

• invalidCells只用於檢測死角，但由於前一點，我會放棄它的使用。

我假設你的目標是在visited陣列表示最短路徑最終到達細胞，從它刪除了所有可能的變少走彎路。通過BFS實現這一目標的方式是使用隊列不僅存儲位置，而且還可以使用導致這些位置的最短路徑。然後，當你點擊結束單元格時，可以返回該單一路徑，忽略可能仍在隊列中的所有其他路徑。

注意，這裏是你的榜樣了一個問題：最終單元標記爲1，和你的代碼不會檢測到這樣的小區的最終單元，而是會繞着它走，從來沒有發現它。要麼確保結束單元總是標記爲0，要麼在執行任何其他檢查之前執行結束單元測試。

這裏有變化，使你的代碼 - 看到這些評論。

var matrix = [ 
 
    [0, 1, 0, 1, 0], 
 
    [0, 0, 1, 0, 0], 
 
    [0, 0, 1, 1, 0], 
 
    [0, 0, 0, 0, 0], 
 
    [0, 1, 0, 1, 0] 
 
]; 
 

 
var start = [4, 0]; 
 
var end = [3, 4]; 
 

 
function findWay(position, end) { 
 
    var queue = []; 
 

 
    matrix[position[0]][position[1]] = 1; 
 
    queue.push([position]); // store a path, not just a position 
 

 
    while (queue.length > 0) { 
 
    var path = queue.shift(); // get the path out of the queue 
 
    var pos = path[path.length-1]; // ... and then the last position from it 
 
    var direction = [ 
 
     [pos[0] + 1, pos[1]], 
 
     [pos[0], pos[1] + 1], 
 
     [pos[0] - 1, pos[1]], 
 
     [pos[0], pos[1] - 1] 
 
    ]; 
 

 
    for (var i = 0; i < direction.length; i++) { 
 
     // Perform this check first: 
 
     if (direction[i][0] == end[0] && direction[i][1] == end[1]) { 
 
     // return the path that led to the find 
 
     return path.concat([end]); 
 
     } 
 
     
 
     if (direction[i][0] < 0 || direction[i][0] >= matrix[0].length 
 
      || direction[i][1] < 0 || direction[i][1] >= matrix[0].length 
 
      || matrix[direction[i][0]][direction[i][1]] != 0) { 
 
     continue; 
 
     } 
 

 
     matrix[direction[i][0]][direction[i][1]] = 1; 
 
     // extend and push the path on the queue 
 
     queue.push(path.concat([direction[i]])); 
 
    } 
 
    } 
 
} 
 

 
var path = findWay(start, end); 
 
console.log(JSON.stringify(path));