递归洪水填充 - 检查边界

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); 
    } 
}