计算房间数量的洪水填充算法

Question

我正在尝试制作一个洪水填充算法来计算被墙包围的空白空间的数量。我使用的是二维字符串数组，墙壁由“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

懒得尝试你的代码，但这里有一些东西（有些已经在评论中提到）：

你在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);

你灌什么阵?

我不是JAVA编码员所以我在这个中可能是错误的但是如果我使用C++类比那么：
```
public static void getNumOfRooms(String map[][])
```
将创建 map[][] 的新本地副本，因此您正在访问内部的本地副本（除非它意味着指针而不是数组副本）。因此，您可能正在检查本地副本中的值，但您的洪水填充正在访问原始地图：
```
public static void floodFill(int x, int y, String oldChar,  String newChar)
```
因此，本地 map[][] 的任何变化都不会导致您计算的是 space 的数量，而不是房间的数量。我会从 getNumOfRooms header 中删除 String map[][] 操作数来补救。
你忘了背景

大多数房间布局都有不属于任何房间的外边框 space。因此，您应该扫描地图中最外面的矩形，如果发现任何 space，请在计算房间之前用墙字符或一些临时字符填充它，以避免将其计为房间。您将计数器设置为 -1 而不是不正确的（如果没有外部 space 怎么办）它应该是 0.
使用 null 字符

在某些情况下，在字符串中使用 null 字符可能很危险，因为某些字符串操作将其用作字符串终止符。不确定你的 JAVA string 是否也是这种情况，但如果是，例如在第一条地图线中通常是外部 space 所以行可能以 null 开头，这可以将 map[0].length 更改为零，以进行某些破坏地图布局的操作。我会使用 ASCII space </code> 而不是它更安全，而且打印出 <code>map 也更容易。

计算房间数量的洪水填充算法

Flood Fill Algorithm that counts rooms

java

algorithm

dictionary

flood-fill

multidimensional-array