计算房间的洪水填充算法

Question

我正在尝试制作一种洪水填充算法，该算法可以计算被墙壁包围的空白空间的数量。我正在使用 2D 字符串数组，墙壁由"1"表示，空格为空。理想情况下，算法应该检查数组中的每个字符串，在位置 map[x][y] 的字符串不为空的任何时候返回，并计算被墙壁包围的空白空间的数量。然而，目前我得到的房间数量非常长，不确定我哪里出了问题。

public static void floodFill(int x, int y, String oldChar,  String newChar){
     x = 0;
     y=0;

    if (x < 0 || y < 0 || x > map.length || y > map[0].length ){
        return;
    }
     if (map[x][y] != oldChar){
         return;
     }
     map[x][y] = newChar;

     // Recursive calls

         floodFill(x - 1, y, oldChar, newChar);
         floodFill(x +1, y, oldChar, newChar);
         floodFill( x, y-1, oldChar, newChar);
         floodFill(x, y+1, oldChar, newChar);

     }
public static void getNumOfRooms(String map[][]){
     roomCount = -1;
     for(x = 0; x < map.length; x++){
         for (y = 0; y < map[0].length; y++){
             if (map[x][y] == null){
                 floodFill(x, y, null, "x");
                 roomCount+=1;
                 System.out.println(map);
             }
     }
 }

Answer 1

懒得尝试你的代码，但这里有一些事情(有些已经在评论中提到(：

1. 您在检查递归调用map[][]内缺失

   是的，你得到了这个：

   if (x < 0 || y < 0 || x > map.length || y > map[0].length ) return;
   

   但这并不好(甚至无用(，因为您的递归调用最多可以访问+2并-1索引越界。也应该>= map[0].length.如果完全删除它，我会删除它，而是使用：

   if (x>              0) floodFill(x-1,y, oldChar, newChar);
   if (x<map   .length-1) floodFill(x+1,y, oldChar, newChar);
   if (y>0)               floodFill(x,y-1, oldChar, newChar);
   if (y<map[0].length-1) floodFill(x,y+1, oldChar, newChar);
   

2. 你在填充什么阵列？

   我不是 JAVA 编码人员，所以我可能错了，但如果我使用C++类比，那么：

   public static void getNumOfRooms(String map[][])
   

   将创建新的map[][]本地副本，以便您访问内部的本地副本(除非它意味着指针而不是数组副本(。因此，您可能正在检查本地副本中的值，但您的洪水填充正在访问原始地图：

   public static void floodFill(int x, int y, String oldChar,  String newChar)
   

   因此，本地map[][]的变化不会导致您计算的是空间数量而不是房间。我会从标头中删除String map[][]操作数getNumOfRooms以解决此问题。

3. 你忘记了背景

   大多数房间布局具有不属于任何房间的外部边框空间。因此，您应该扫描地图中最外层的矩形，如果找到任何空间，请在计数房间之前用墙壁字符或一些临时字符填充它，以避免将其计为房间。您将计数器设置为-1，这是不正确的(如果没有外层空间怎么办(，它应该0。

4. 使用null字符

   在某些情况下null字符串中使用字符可能很危险，因为某些字符串操作将其用作字符串终止符。不确定您的 JAVA string是否也是如此，但如果是，例如在第一条地图行中通常是外太空，因此该行可能以 null 开头，这可能会将map[0].length更改为零对于某些操作破坏地图布局。我会使用 ASCII 空间代替它更安全，而且打印出CC_17也容易得多。