0

我在矩阵中有一个合法邻居的递归洪水填充(合法邻居是具有相同颜色的邻居),洪水没有填充数组中的所有合法邻居。我用于测试的板是:

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
4

2 回答 2

1

你有几个错误。首先,你的守卫不包括第 0 行和第 0 列,所以这就是你没有得到预期结果的原因之一。

现在,修复您将获得堆栈溢出的问题,因为您将尝试填充所有邻居,无论它们具有哪种颜色。这意味着您将永远访问颜色为 0 的所有单元格。您只想填充具有oldColor的邻居。

最后,您的方法需要参数row, column,但您使用column, row递归调用它,因此您切换每个堆栈级别的索引。

修复了您可以在没有保护的情况下获得更简单的方法if。如果您希望行的长度不同,则需要再次添加防护。

显示一个自包含的示例,该示例在填充地图之前和之后打印地图。

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);
  }
}
于 2012-12-19T21:36:38.593 回答
0

这不是最佳答案,但我无法删除我的提交。

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("}");
        }
    }
}
于 2012-12-19T21:30:22.020 回答