I'm creating a method that takes a 2D array and scans throughout the array to find "Chunks" of numbers that are completely surrounded by zeros and convert those Chunks (I call them the islands) into zeros.
I'm trying to delete all of the "islands" except for the largest one.
For example, for this 2D array
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
After the method the 2D array should now be:
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
the small chunk of 1 2 is "deleted"
Here is a second example, as the method should also take chunks of numbers that are not part of the "main" chunk as Islands and that are on the edges as well.
The original array would be:
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
After the method execution, it should be:
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
In this case, the island
1 2 3
3 2
is deleted because it is separate from the big chunk and is surrounded by zeros.
The following code is the one I have so far, and it does not work as intended. It's wrong because I believe that it's taking the main chunk as an Island, and what happens is that it converts the entire array into zeros instead of deleting only the small Islands. It includes an example, and you should see what It does when you run it.
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();
}
}
}
Any idea of what should I change?
CodePudding user response：
This looks like a flood-fill problem which you've already implemented, so the issue now is how do you determine which chunk to keep and which ones to remove.
My first thought towards implementation would be to create a hashmap containing a starting point (I'd imagine the upper-leftmost coordinate) for each island, along with its size (determine this by modifying your flood-fill algorithm to have a running count while traversing an island). You could then sort the hashmap by the island size and call deleteIsland on every island that isn't the largest.
CodePudding user response：
This problem can be solved in linear time by treating the cells of the given Matrix as the Vertexes of an undirected disjointed Graph.
The task boils down to exploring all connected Components (islands) in a Graph, and comparing them with each other.
And for that we would need to implement of the Graph-traversal algorithms. I've chosen the Depth first search algorithm for that purpose.
For convenience, I've made several changes to your DestroyIslands class:
- Introduced an inner class
Island, which wraps a list of cells that constitute an Island (*Connected component of the Graph). This class implementsComparablein based on size of the cells to make it easier to find the largest Island. And defines the methoddestroy()to nullify the rest Islands. - Introduced a
staticarrayNEIGHBOURSof typeint[][]representing all possible adjacent cells, which should be considered while iterating through the matrix from left to right and from top to bottom. - Reference to the Matrix is stored in the instance field
grid, and all methods ofDestroyIslandsa defined as instance methods.
That's how implementation might look like:
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();
}
}
}
main()
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();
}
Output:
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