遞歸函數返回早期只檢查一個路徑

Question

我正在創建一個連接四個遊戲，我正在使用遞歸來檢查所做的移動是否是一個勝利的舉動。 x和y是在7x6網格上移動的座標。

我還沒有實施檢查點的方向是否正確匹配（所以現在如果4件以任何方式接觸，它應該仍然檢測到勝利）。但在我這樣做之前，我遇到了一個問題。即使做出的舉動應該會贏得勝利，如果有另外一條路線沒有連續四條，該函數將返回false。

的功能不正確檢測不到勝利示例（綠線是什麼應該被檢測到，紅線是我認爲的功能把返回虛假提前路徑）：https://prnt.sc/fjhia1

這是我的代碼：

function isVisited(x,y,visited){ 
    var pointStr = x + "," + y; 
    var result = visited.some(function(e){ 
     return e.join() == pointStr; 
    }); 
    return result; 
} 

function checkWin(x, y, color, visited, count) { 
    if(count==3) return true; 
    for(i=-1; i<2; i++) { 
     for (j=-1; j<2; j++) { 
      if(!(i==0 && j==0) && (x+i)<7 && (y+j)<6 && (x+i)>-1 && (y+j)>-1 && grid[x+i][y+j] != null) { 
       if (grid[x+i][y+j] == color && !isVisited(x+i,y+j,visited)) { 
        visited.push([x, y]); 
        if(checkWin(x+i, y+j, color, visited, count+1)) return true; 
       } 
      } 
     } 
    } 
    return false; 
} 

爲了澄清，我和j是用來檢查起點周圍所有點的偏移量。

顏色參數是「黑色」或「紅色」。網格是一個7x6的二維數組，用於存儲哪些球員在哪裏，並在球員進行移動時更新。整個checkWin（）函數在每次移動後都會調用，其中x和y參數是剛剛播放的移動的座標。鏈接的圖片中顯示了陣列中的顏色示例。

從圖像

電網樣品，這應該通過成爲checkWin（）返回true爲x = 5，y = 3，顏色= 「黑」，但事實並非如此：

[[null,null,null,null,null,null],[null,null,null,null,null,null],[null,null,null,null,null,null],[null,null,null,null,null,"black"],[null,null,null,null,"black","red"],[null,null,null,"black","black","black"],[null,null,null,"red","red","red"]] 

Answer 1

這是一些工作代碼。我試圖把你的grid加入代碼中。

你的代碼有幾個問題，但我認爲主要的是你沒有正確地總結計數。在你的代碼，你會碰到這樣的情況：

starting here 
    | 
    v 
R R R R 

首先您探索這個節點的左邊，你會發現有不連續4個紅。然後你會向右邊探索，發現連續沒有四個紅色。但你需要做的是總和這些。您需要對起始節點進行計數，然後將左邊的兩個計數到右邊的兩個，以獲得連續四個正確的總數。

以下代碼採用該策略。這是一個重寫，但我試圖保持它有點類似於你的原代碼。如果不清楚，請告訴我。 （此代碼，像你這樣的，並不真正關心 「連續」，而只是 「接觸」。）

const N = null, B = "black", R = "red"; 
 
const grid = [ 
 
// 0 1 2 3 4 5 6 
 
    [N, N, N, N, N, N, N], // 0 
 
    [N, N, N, N, N, N, N], // 1 
 
    [N, N, N, N, N, N, N], // 2 
 
    [N, N, N, N, N, B, R], // 3 
 
    [N, N, N, N, B, B, R], // 4 
 
    [N, N, N, B, R, B, R], // 5 
 
]; 
 

 
function isVisited(x, y, visited) { 
 
    var pointStr = [x, y].join(); 
 
    return visited.some(function (e) { 
 
     return e.join() == pointStr; 
 
    }); 
 
} 
 

 
function checkWin(x, y) { 
 
    function countNeighbors(x, y, color, visited) { 
 
     if (y > 5 || x > 6) { // out of bounds 
 
      return 0; 
 
     } 
 

 
     if (isVisited(x, y, visited)) { // already visited 
 
      return 0; 
 
     } 
 
     visited.push([x, y]); 
 

 
     if (grid[y][x] !== color) { // wrong color 
 
      return 0; 
 
     } 
 

 
     var count = 1; // Count ourselves first. 
 

 
     // For each neighbor, 
 
     for (var i = -1; i < 2; i++) { 
 
      for (var j = -1; j < 2; j++) { 
 
       // add the count starting at that neighbor. 
 
       count += countNeighbors(x+i, y+j, color, visited); 
 
      } 
 
     } 
 

 
     // Return the total found. 
 
     return count; 
 
    } 
 

 
    // There's a win if the count is at least four. 
 
    return countNeighbors(x, y, grid[y][x], []) >= 4; 
 
} 
 

 
console.log(checkWin(3, 5)); // true 
 
console.log(checkWin(5, 3)); // true 
 
console.log(checkWin(6, 3)); // false

Answer 2

你」將錯誤的網格單元索引重新推向visited列表。它應該是[x + i, y + j]。

或者，您可以將語句移到該函數的頂部並保持原樣，這在我看來更好。函數本身檢查一個單元格，並且將該單元格標記爲在啓動時檢查或訪問它更有意義。