计算矩阵中的零岛

本文介绍了计算矩阵中的零岛的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试按照著名的计数岛问题进行编程.

I am trying to program following well-known counting islands problem.

它没有给我预期的输出.我哪里错了?我的假设是如果 0 接触矩阵的第 0 行或列或维度 .. 它不会被视为岛

and it is not giving me the expected output. Where am I going wrong? My assumption is if 0's touch 0th row or column or dimension of matrix .. it will not be treated as island

这是我的代码

public class Matrix { static int rowCount = 5; static int columnCount = 4; static int[][] matrix = { {1,1,1,1,1}, {1,0,0,0,1}, {1,1,1,1,1}, {1,1,1,0,1} }; static boolean[][] visited = new boolean[rowCount][columnCount]; private static int countIslands = 0; public static void main(String[] args) { try{ for(int i=0; i<rowCount; i++){ for(int j=0; j<columnCount; j++){ if(matrix[i][j]==0){ checkZeros(matrix, i, j); System.out.println("returned " + i + j); } } } System.out.println(visited); }catch(Exception e){ } System.out.println(countIslands); } private static void checkZeros(int[][] matrix2, int i, int j) { boolean valueWithinLimits = withinLimits(i,j); System.out.println("checking for " + i + j); if(valueWithinLimits) && checkAlreadyVisited(i,j)){ if(matrix[i][j+1]==0){ checkZeros(matrix2, i, j+1); } if(matrix[i+1][j+1]==0){ checkZeros(matrix2, i+1, j+1); } if(matrix[i+1][j]==0){ checkZeros(matrix2, i+1, j); } if(matrix[i+1][j-1]==0){ checkZeros(matrix2, i-1, j-1); } visited[i][j] = true; System.out.println("i reached here when ij are : " + i + j); countIslands ++; } } private static boolean checkAlreadyVisited(int i, int j) { System.out.println("visited found for " + i + j); return visited[i][j-1] || visited[i-1][j-1] || visited[i-1][j] || visited[i-1][j+1]; } private static boolean withinLimits(int i, int j) { return (i>0 && i<rowCount-1 && j>0 && j<columnCount-1); } }

推荐答案

以下解决方案经过测试，适用于任何可能性

The below solution is tested and works perfectly fine for any possibility

package com.divyanshu.island; /** * <b>Assumption 1 : 1 is Land, 0 is water.</b> * <b>Assumption 2 : It is all water outside the matrix.</b> * * Instantiate IslandCounter by passing a m*n matrix. * Method getIslandCount gives you the count of island formed. * * </br></br>Or</br></br> * * Method getIslandCount gives the count of all connected 1s in a m*n matrix with values in 1 or 0. */ public class IslandCounter { private Integer[][] matrix; public IslandCounter(Integer[][] matrix) { this.matrix = matrix; } public int getIslandCount() { int count = 0; if (matrix == null || matrix.length == 0) { return count; } Integer[][] tempMatrix = matrix.clone(); for (int i = 0; i < tempMatrix.length; i++) { for (int j = 0; j < tempMatrix[i].length; j++) { if (detectIsland(tempMatrix, false, i, j, matrix.length - 1, matrix[i].length - 1)) { count++; } } } return count; } private boolean detectIsland(Integer[][] tempMatrix, boolean islandDetected, int i, int j, int iMax, int jMax) { if (i > iMax || j > jMax || i < 0 || j < 0 || tempMatrix[i][j] == 0) { return islandDetected; } else { tempMatrix[i][j] = 0; islandDetected = true; detectIsland(tempMatrix, islandDetected, i - 1, j, iMax, jMax); detectIsland(tempMatrix, islandDetected, i, j - 1, iMax, jMax); detectIsland(tempMatrix, islandDetected, i + 1, j, iMax, jMax); detectIsland(tempMatrix, islandDetected, i, j + 1, iMax, jMax); } return islandDetected; } } =================================================================================== /** * */ package com.divyanshu.island; import java.util.Random; /** *This is a Main-Class to test the IslandCounter. */ public class IslandTest { /** * @param args */ public static void main(String[] args) { Integer[][] matrix = generateMatrix(); printMatrix(matrix); IslandCounter counter = new IslandCounter(matrix); System.out.println("Total islands in the matrix : " + counter.getIslandCount()); } private static Integer[][] generateMatrix() { Integer[][] matrix = new Integer[4][4]; Random random = new Random(); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { matrix[i][j] = random.nextInt(2); } } return matrix; } private static void printMatrix(Integer[][] matrix) { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { System.out.print(matrix[i][j] + " "); } System.out.println(); } } }