如何在Java中删除2D数组中的数字“岛屿”

Question

我正在创建一个方法，它接受一个二维数组并扫描整个数组以查找被零完全包围的数字“块”，并将这些块（我称之为岛屿）转换为零。

我试图删除除最大岛屿外的所有“岛屿”。

例如，对于这个二维数组：

1 2 3 2 2 1 
3 2 2 1 2 3
3 2 2 1 3 2
2 3 2 3 2 2
2 2 3 1 1 2
3 2 1 2 3 2
2 3 1 2 3 2
2 2 0 0 0 0
0 0 0 1 2 0
0 0 0 0 0 0 

在这个方法之后，2D数组应该是这样的：

1 2 3 2 2 1 
3 2 2 1 2 3
3 2 2 1 3 2
2 3 2 3 2 2
2 2 3 1 1 2
3 2 1 2 3 2
2 3 1 2 3 2
2 2 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0 

小片段1 2 被"删除"

这是第二个例子，因为该方法应该将不属于“主”片段的数字块和位于边缘的岛作为单独的块来处理。

原始数组如下：

1 2 3 2 2 1 
3 2 2 1 2 3
3 2 2 1 3 2
2 3 2 3 2 2
2 2 3 1 1 2
3 2 1 2 3 2
2 3 1 2 3 2
2 2 0 0 0 0
0 0 0 1 2 3
0 0 0 0 3 2 

方法执行后，应该是这样的：

1 2 3 2 2 1 
3 2 2 1 2 3
3 2 2 1 3 2
2 3 2 3 2 2
2 2 3 1 1 2
3 2 1 2 3 2
2 3 1 2 3 2
2 2 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0 

在这种情况下，岛屿。

1 2 3 
  3 2

被删除的原因是它与大块分开，被零包围。

以下是我目前拥有的代码，但它并没有按预期工作。这是错误的，因为我认为它将主要块视为孤岛，结果是将整个数组转换为零，而不仅仅是删除小的孤岛。它包括一个示例，当您运行它时，您应该看到它的效果。

public class destroyIslands {
    public static void main(String[] args) {
        int[][] example = { {1, 2, 3, 1, 2},
                            {2, 3, 2, 1, 2},
                            {3, 2, 1, 2, 2},
                            {0, 2, 0, 0, 0},
                            {0, 0, 0, 2, 1} };
        
        example = deleteIslandBoard(example);
        printGrid(example);
    }
    
    public static int[][] deleteIslandBoard(int[][] array) {
      // Create a boolean array to track which cells have been visited
      boolean[][] visited = new boolean[array.length][array[0].length];
    
      // Iterate 
      for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[0].length; j++) {
            // If the cell is not visited and is part of an island
            if (!visited[i][j] && array[i][j] != 0) {
                // Delete the island by setting all cells to 0
                deleteIsland(array, i, j, visited);
            }
        }
      }
      // Return the modified array
      return array;
    }

    public static void deleteIsland(int[][] array, int i, int j, boolean[][] visited) {
      // Check if the current cell is out of board or if it has already been visited
      if (i < 0 || i >= array.length || j < 0 || j >= array[0].length || visited[i][j]) {
        return;
      }
      // Mark the current cell as visited
      visited[i][j] = true; // If the current cell is part of the island, set it to 0
      if (array[i][j] != 0) {
        array[i][j] = 0;
        // Recursively delete the neighboring cells that are part of the island
        deleteIsland(array, i - 1, j, visited);
        deleteIsland(array, i + 1, j, visited);
        deleteIsland(array, i, j - 1, visited);
        deleteIsland(array, i, j + 1, visited);
      }
    }
    
    public static void printGrid(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }
}

你有什么想法需要改变吗？

- MazaPan616

---

所以问题是你想删除除了最大的岛屿之外的所有岛屿？这是一个常数还是每次都会随机变化？ - Justin Adams

是的，那正是我想要做的。如果你所说的“板子上的数字”是一个常数，那不是这样的。这个板子将会被随机生成，但这不会成为一个问题，因为如果代码不能在给定的例子中运行，它也不能在任何板子上运行。 - MazaPan616

对角相邻的非零单元格被视为相连，还是只有水平或垂直相邻的单元格可以形成一个岛屿？ - Alexander Ivanchenko

我还不确定，但是你的任务看起来像是使用 https://en.wikipedia.org/wiki/Disjoint-set_data_structure 一种良好的应用。其思想是遍历数组中的所有点，并将它们分配到各个集合中。这样，您就可以将数组中的所有点分散到多个集合中。然后只需找到最大的集合并删除其他所有集合即可。 - chptr-one

我的程序中，只有水平或垂直相邻的单元格才能形成一个岛屿。不要计算对角线。中间行永远不会完全为空。 - MazaPan616

Answer 1

这个问题可以通过将给定矩阵的单元格视为一个无向不相交图形的顶点来在线性时间O(n)内解决。

任务归结为探索图中所有连通分量（岛屿）并将它们彼此比较。

为此，我们需要实现图遍历算法。我选择了深度优先搜索算法。

为了保持简单，图的一个顶点将表示为包含单元格坐标的两个元素的int[]数组（可以通过定义一个专门的顶点类来重新实现，并通过保存对顶点集合的引用使每个顶点知道其邻居）

为了方便起见，我对您的DestroyIslands类进行了几个更改：

• 引入了一个内部类Island，它包装了构成岛屿（图的连通分量）的单元格列表。该类实现了Comparable接口，基于单元格的大小进行比较，以便更容易地找到最大的岛屿。并定义了destroy()方法来使其余的岛屿无效。
• 引入了一个static数组NEIGHBOURS，类型为int[][]，表示在从左到右和从上到下遍历矩阵时应考虑的所有可能相邻单元格。
• 对矩阵的引用存储在实例字段grid中，并且DestroyIslands的所有方法都被定义为实例方法（如果您想将它们保持static，请随意根据需要更改它们，如果您掌握算法本身，这将很容易）。

以下是实现的样子：

public class DestroyIslands {
    public static final int[][] NEIGHBOURS = // adjacent cells
        {{0, 1},   // horizontal -
         {1, 0},   // vertical   |
         {1, 1},   // diagonal   \
         {1, -1}}; // diagonal   /

    private List<Island> islands = new ArrayList<>(); // collection of Islands
    private int[][] grid; // matrix
    
    public DestroyIslands(int[][] grid) {
        this.grid = grid;
    }
    
    public class Island implements Comparable<Island> {
        private List<int[]> cells = new ArrayList<>();
        
        public void addCell(int[] cell) {
            cells.add(cell);
        }
        
        public void destroy() {
            cells.forEach(cell -> grid[cell[0]][cell[1]] = 0);
        }
        
        @Override
        public int compareTo(Island other) {
            return Integer.compare(cells.size(), other.cells.size());
        }
    }
    
    public void deleteIslandBoard() {
        exploreIslands();
        deleteSmallerIslands();
    }
    
    public void exploreIslands() {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                
                if (!visited[i][j] && grid[i][j] != 0) { // if a New Island was found
                    exploreIsland(new int[]{i, j}, visited); // explore the Island, i.e. index all its cell and mark them as visited
                }
            }
        }
    }
    
    /**
     * Depth first search implementation
     */
    public void exploreIsland(int[] cell, boolean[][] visited) {
        Island island = new Island();
        islands.add(island); // updating the list of Islands
        
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(cell);
        
        while (!stack.isEmpty()) {
            int[] next = stack.poll();
            island.addCell(next);
            
            for (int[] shift : NEIGHBOURS) {
                int row = next[0] + shift[0];
                int col = next[1] + shift[1];
                
                if (isValid(row, col) && !visited[row][col]) { // if cell exist, non-zero and not visited yet
                    stack.push(new int[]{row, col});
                    visited[row][col] = true;
                }
            }
        }
    }
    
    public boolean isValid(int row, int col) {
        return row >= 0 && row < grid.length
            && col >= 0 && col < grid[0].length
            && grid[row][col] != 0;
    }
    
    public void deleteSmallerIslands() {
        if (islands.isEmpty()) return; // otherwise Collections.max() would throw NoSuchElementException

        Island largest = Collections.max(islands);
        for (Island next : islands) {
            if (next != largest) next.destroy();
        }
    }
    
    public void printGrid() {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }
}

主函数()

public static void main(String[] args) {
        int[][] example = {
            {1, 2, 3, 1, 2},
            {2, 3, 2, 1, 2},
            {3, 2, 1, 2, 2},
            {0, 2, 0, 0, 0},
            {0, 0, 0, 2, 1}};
        
        DestroyIslands destroyIslands = new DestroyIslands(example);
        destroyIslands.deleteIslandBoard();
        destroyIslands.printGrid();
    }

输出：

1 2 3 1 2 
2 3 2 1 2 
3 2 1 2 2 
0 2 0 0 0 
0 0 0 0 0

在线演示链接

- Alexander Ivanchenko

---

@MazaPan616 抱歉，我有一个对称的问题：你能更具体地说明你不理解什么吗？你查看了链接吗？如果在维基百科中找到的链接文章让你感到困惑，我可以添加一个简要的说明来实现DFS算法。但是你必须说出你困惑的重点。 - Alexander Ivanchenko

抱歉造成误解。我不熟悉这种类型的代码，我想知道如何将此输出打印到控制台？ - MazaPan616

@MazaPan616 我已经使用了你的方法 printGrid() (唯一的改变是，我去掉了 static 修饰符, 需要创建一个类型为 DestroyIslands 的对象才能使用它，答案中使用的所有代码均已提供)。你是否对实例方法的使用感到困惑，而不是使用 static 方法呢？ - Alexander Ivanchenko

我之前不明白为什么我的控制台上没有任何显示，后来发现是因为我不知道需要导入哪些软件包，但最终找到了解决方法。现在代码可以正常运行了。谢谢！ - MazaPan616

让我们在聊天中继续这个讨论。 - MazaPan616

Answer 2

这看起来像是一个洪水填充问题，你已经实现了它，现在的问题是如何确定哪些块要保留，哪些要删除。

我的第一个想法是创建一个哈希表，其中包含每个岛屿的起始点（我想象中的左上角坐标）以及其大小（通过修改你的洪水填充算法，在遍历岛屿时计算大小）。然后，你可以按岛屿大小对哈希表进行排序，并在除最大岛屿外的每个岛屿上调用deleteIsland函数。

- Justin Adams