Maz*_*616 8 java arrays algorithm math for-loop
我正在创建一种方法，该方法采用 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 1 2 0
0 0 0 0 0 0
在该方法之后，二维数组现在应该是：
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();
}
}
}
知道我应该改变什么吗？
通过将给定矩阵的单元视为无向不相交图的顶点，可以在线性时间O(n)内解决此问题。
该任务归结为探索图中所有连接的组件（岛），并将它们相互比较。
为此，我们需要实现图遍历算法。为此，我选择了深度优先搜索算法。
为了简单起见，图的顶点将表示为int[]包含单元格坐标的两个元素的数组（请随意通过为顶点定义单独的类来重新实现它，以使每个顶点通过持有引用来了解其邻居到顶点的集合）
为了方便起见，我对您的DestroyIslands课程做了一些更改：
Island，它包装了构成岛（图的连通组件）的单元格列表。此类Comparable根据单元格的大小实现，以便更容易找到最大的岛屿。destroy()并定义了使其余岛屿无效的方法。static，在从左到右、从上到下迭代矩阵时应考虑这一点。NEIGHBOURSint[][]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();
}
}
}
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();
}
输出：
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