遞歸洪水填充 - 檢查邊界

Question

我有一個矩陣中的合法鄰居的遞歸洪水填充（合法鄰居是一個具有相同顏色的鄰居），洪水沒有填充數組中的所有合法鄰居。 使用用於測試`米的板是：

int[][] map={{4,0,0,0}, 
      {0,4,0,0}, 
      {0,4,0,0}, 
      {0,4,0,0}}; 

    fill(map,1,1,9,4);// calling to function. 

輸出爲：

4000 
0900 
0900 
0900 

編輯 如果我真的改變地圖到：

int[][] map={{4,0,0,0}, 
     {4,4,0,0}, 
     {0,4,0,0}, 
     {0,4,0,0}}; 

輸出將是：

4000 
4900 
0900 
0900 

兩個左4號需要太填補。 和我的遞歸函數是：

public static void fill(int[][] map, int row, int col, int color,int oldColor) 

    { 

System.out.println("row is: "+row+"col is:"+col); 
if ((row <= 0) || (row >= map.length) || (col <= 0) || (col >= map.length)) return; 

if(map[row][col]==color) 
     return; 

if(map[row][col]==oldColor) 
    { 
     map[row][col]=color; 
    } 
if(col+1<=map.length) 
     fill(map, col+1, row,color,oldColor); 
if((col-1)<=0) 
     fill(map,col-1, row,color,oldColor); 

    if(row+1<=map.length) 
     fill(map, col, row+1,color,oldColor); 
    if((row-1)<=0) 
     fill(map, col, row-1,color,oldColor); 

    } 

更改代碼

public static void fill(int[][] map, int row, int col, int color,int oldColor) { 
    System.out.println("row is: "+row+"col is:"+col); 
if ((row < 0) || (row > map.length) || (col < 0) || (col > map.length) || map[row]      [col]!=oldColor) return; 

if(map[row][col]==color) 
     return; 

if(map[row][col]==oldColor) 
    { 
     map[row][col]=color; 
    } 

fill(map, col, row-1,color,oldColor); 
fill(map, col+1, row,color,oldColor); 
    fill(map, col, row+1,color,oldColor); 
    fill(map,col-1, row,color,oldColor); 
    } 

現在的輸出是：

9000 
9900 
0900 
0400 

Answer 1

這不是最好的答案，但我不能刪除我的提交。

public class Fill 
{ 

    public static void fill(int[][] map, int col, int row, int color,int oldColor) 
    { 

     System.out.println("row is: "+row+"col is:"+col); 
     if ((row <= 0) || (row >= map.length) || (col <= 0) || (col >= map.length)) return; 

     if(map[row][col]==color) 
      return; 

     if(map[row][col]==oldColor) 
     { 
      map[row][col]=color; 
     } 

     if(col+1<=map.length) { 
      fill(map, col+1, row,color,oldColor); 
     } 

     if((col-1)<=0) { 
      fill(map,col-1, row,color,oldColor); 
     } 

     if(row+1<=map.length) { 
      fill(map, col, row+1,color,oldColor); 
     } 

     if((row-1)<=0) { 
      fill(map, col, row-1,color,oldColor); 
     } 

    } 


    public static void main(String pArgs[]) 
    { 
     int[][] map={{4,0,0,0}, 
      {0,4,0,0}, 
      {0,4,0,0}, 
      {0,4,0,0}}; 

     printMap(map); 
     fill(map,1,1,9,4);// calling to function. 
     printMap(map); 
    } 

    static void printMap(int[][] map) 
    { 
     for (int i=0; i < 4; i++) { 
      System.out.print("{"); 
      for (int j=0; j<4; j++) { 
       System.out.print(map[i][j] + ","); 
      } 
      System.out.println("}"); 
     } 
    } 
} 

Answer 2

你有幾個錯誤。首先，你的警衛不包括第0行和第0列，所以這就是你沒有得到預期結果的原因之一。

現在，修復你會得到一個堆棧溢出，因爲你會嘗試填充所有的鄰居，不管他們有什麼顏色。這意味着你將永遠訪問顏色爲0的所有單元格。您只想填充具有oldColor的鄰居。

最後，你的方法需要的參數行，列，但你recursivly與列調用它，排，讓你切換索引每個堆棧的水平。

修復你可以得到一個更簡單的方法沒有防範如果。如果你期望行數不同，那麼你需要重新添加警戒。

顯示一個自包含的示例，可以在填充地圖之前和之後打印地圖。

public class FloodFill { 

    static int[][] map1 ={{4,0,0,0}, {4,4,4,4}, {0,4,0,4}, {0,4,0,0}}; 
    static int[][] map2 ={{0,4,4,4}, {0,4,0,4}, {0,4,0,4}, {9,9,9,4}}; 

    public static void fill(int[][] map, int row, int col, int color, int oldColor) { 
    if (map[row][col] == oldColor) { 
     map[row][col] = color; 
     if (col + 1 < map[row].length) 
     fill(map, row, col + 1, color, oldColor);   
     if (col > 0) 
     fill(map, row, col - 1, color, oldColor);   
     if (row + 1 < map.length) 
     fill(map, row + 1, col, color, oldColor); 
     if (row > 0) 
     fill(map, row - 1, col, color, oldColor); 
    } 
    } 

    public static void main(String[] args) { 
    floodfill(map1); 
    floodfill(map2); 
    } 

    private static void floodfill(int[][] map) { 
    show(map, "Initial"); 
    fill(map, 1, 1, 9, 4); 
    show(map, "Filled"); 
    } 

    private static void show(int[][] map, String label) { 
    System.out.println(label); 
    for (int[] row : map) { 
     for (int val : row) { 
     System.out.print(val + " "); 
     } 
     System.out.println(); 
    } 
    } 
} 

一個替代的填充與警衛，然後也處理不同長度的行。

public static void fill2(int[][] map, int row, int col, int color, int oldColor) { 
    if (row < 0 || row >= map.length || col < 0 || col >= map[row].length) 
    return; 
    if (map[row][col] == oldColor) { 
    map[row][col] = color; 
    fill2(map, row, col + 1, color, oldColor);   
    fill2(map, row, col - 1, color, oldColor);   
    fill2(map, row + 1, col, color, oldColor); 
    fill2(map, row - 1, col, color, oldColor); 
    } 
}