如何在這個函數中正確使用遞歸？

好吧，我有這個函數，需要使用遞歸，在用戶的座標（i，j）爲零的情況下，在mineswepper（int [] [] m）中搜索。零意味着該地區附近沒有地雷。如果它是零，那麼我的函數應該在一個區域範圍內顯示這個零和圍繞這個初始零點的零點。這必須以遞歸的方式進行，找到所有的零。如何在這個函數中正確使用遞歸？

我的int [] [] v是我的視覺矩陣，它用於爲所有位置分別給出和狀態（1 =>您可以顯示位置，0 =>保留？），所以當我全部打印在矩陣m中，我們只能看到在矩陣v中具有1的位置。發現零2

2-。搜索四處打聽其他零，直到有沒有更多的零發現

? ? ? ? 
? ? ? ? 
? ? 0 ? 
? ? ? ? 
? ? ? ?

它會是什麼樣子在視覺矩陣V

它會是什麼樣子在視覺矩陣V

0 0 0 0 
0 0 0 0 
0 0 1 0 
0 0 0 1 
0 0 0 0 

public void zeros(int[][]m, int[][]v, int j, int i){ 

      v[i][j] = 1; 

      for(int a = Math.max(0, i-1); a < Math.min(5,i+2); a++){ 
       for(int b = Math.max(0,j-1); b < Math.min(5,j+2); b++){ 
       if(m[a][b] == 0){ 
        i = a; 
        j = b; 
        zeros(m, v, i, j);} 

       } 
      }   
    }

fors將搜索給定的i和j周圍的所有位置。

它顯示了我的錯誤，線程「主」java.lang.StackOverflowError異常。我不明白爲什麼。也許有人可以提供一種方法來實現遞歸，或者告訴我我的錯誤。

來源

2013-09-30 Mac

請證明你已經嘗試過以及它失敗了。 – codethulhu

您有一個5x4的矩陣，所以索引從一個方向從0到4，在另一個方向從0到3。也許錯誤是你正在使用一個索引5，這是超出你的矩陣。 –

@angel_navarro不，OP得到一個'StackOverflowError'，而不是'ArrayIndexOutOfBoundsException'。 –

到目前爲止都很好。但解決以下

刪除這兩條線：

i = a; 
j = b;

調用它如下：的

zeros(m, v, a, b);

代替：

zeros(m, v, i, j);

也改變這一點：

public void zeros(int[][]m, int[][]v, int j, int i)

太：

public void zeros(int[][]m, int[][]v, int i, int j)

這樣做是爲了：

if(m[a][b] == 0 && v[a][b]==0)

來源

2013-09-30 20:09:29 hasan83

i = a，j = b。這裏是主要問題。你缺少循環結束條件 – hasan83

完成，仍然是相同的錯誤 – Mac

你嘗試過嗎？ – hasan83

在你做「m [a] [b] == 0」之前，你需要進行檢查以確保a和b不在m的範圍之外。我認爲你目前沒有做這個檢查。

來源

2013-09-30 20:08:54

他用max和min函數 – hasan83

這聽起來與Flood Fill操作非常相似。 Wikipedia has some meta-code來完成這一點。它不是遞歸的，但應該很好地工作。

來源

2013-09-30 20:09:14

錯誤java.lang.StackOverflowError的是最常見的一個使用遞歸的時候。這意味着你在遞歸中創建了一個無限循環，並且該棧的大小不足以處理所有的遞歸調用。

想想當你在周圍的方塊上遞歸調用你的函數時會發生什麼。因爲你不編輯原始方塊，它會再次被調用，創建一個無限循環。

修復此問題並解決您的問題。

來源

2013-09-30 20:14:18

你傳入i和j遞歸，但你不修改這些變量的值，所以會不斷出現，

來源

2013-09-30 20:17:02

電話使用移動不變考慮我的解決方案：

int [] movx ={-1, -1, -1, 0, 0, 1, 1, 1}; 
int [] movy ={-1, 0, 1, -1, 1, -1, 0, 1};

這是您從(x,y)移動的偏移量。所以，你的方法將是

public void zeros(int[][] m, int[][] v, int x, int y) { 

    //Already visited? 
    if (v[x][y] == 1) return; 

    //Mark as visited 
    v[x][y] = 1; 

    for (int i = 0; i < 8; i++){ 
     //neighbors coordinates 
     int nx = x + movx[i]; 
     int ny = y + movy[i]; 

     //check boundaries 
     if (nx >= 0 && nx < m.length && ny >= 0 && ny < m[x].length){ 

      //if there is no mine check it 
      if (m[nx][ny] == 0) 
       zeros(m, v, nx, ny); 
     } 
    }    
}

例如，如果你有(x=2,y=2)你的鄰居將是：

(x=1,y=1) 
(x=1,y=2) 
(x=1,y=3) 
(x=2,y=1) 
(x=2,y=2) 
(x=2,y=3) 
(x=3,y=1) 
(x=3,y=2) 
(x=3,y=3)

來源

2013-09-30 20:33:31 omainegra

你只帶了4個鄰居。可能這是對的。但我們的朋友花了8. – hasan83

@hasan是的，我修好了，對不起 – omainegra

不錯的解決方案我解決了近100倍的類似問題。用來寫一些與你的解決方案相同的小改動。 – hasan83

我認爲我得到它。

只是在fors中添加這個額外的條件。

如果（M [A] [B] == 0 & & v [A] [B]！= 1）

所以我們不能返回到包含在基質中視力V A 1的任何位置

來源

2013-09-30 20:40:17 Mac

如何在這個函數中正確使用遞歸？

回答

相關問題