Created
November 17, 2018 16:56
-
-
Save jiahaoliuliu/3015e1dabd2b8876be39d0d5a7d5f0c5 to your computer and use it in GitHub Desktop.
SImple algorithm to find the number of islands in a matrix
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Given a matrix of 0 and 1, where 0 represents water and 1 represent land. | |
* Two pieces of land are connected if they are touching each other(vertical, horizontal or diagonal) | |
* Please write a method that counts the number of islands. | |
* | |
* Here is an example : | |
* 0 (1 1) 0 0 0 [1] | |
* 0 (1) 0 0 [1 1] 0 | |
* 0 (1 1) 0 0 [1] 0 | |
* 0 0 0 0 0 0 0 | |
* 0 "1 1 1 1 1" 0 | |
* | |
* The number of islands is three. | |
* Write a method count the number of islands | |
*/ | |
public class NumberOfIslands { | |
static int numberOfIslands(int[][] surface) { | |
int result = 0; | |
for (int i = 0; i < surface.length; i++) { | |
for (int j = 0; j < surface[i].length; j++) { | |
int value = surface[i][j]; | |
if (value == 0) { | |
continue; | |
} else if (value == 1) { | |
if (isFirstElementOfTheIsland(i, j, surface)) { | |
result++; | |
} | |
} | |
} | |
} | |
return result; | |
} | |
/** | |
* Check if it is the first element of an island. This is that for any position previous | |
* to this they are always 0 | |
* 0 0 => true . Otherwise return false | |
* 0 -> 1 | |
* 0 | |
* @param row | |
* @param column | |
* @param surface | |
* @return | |
*/ | |
private static boolean isFirstElementOfTheIsland(int row, int column, int[][]surface) { | |
return isLeftUpDiagonalWater(row, column, surface) && | |
isLeftDownDiagonalWater(row, column, surface) && | |
isPreviousRowWater(row, column, surface) && | |
isPreviousColumnWater(row, column, surface); | |
} | |
private static boolean isPreviousColumnWater(int row, int column, int[][] surface) { | |
if (column == 0) { | |
return true; | |
} | |
return surface[row][column-1] == 0; | |
} | |
private static boolean isPreviousRowWater(int row, int column, int[][] surface) { | |
if (row == 0) { | |
return true; | |
} | |
return surface[row -1][column] == 0; | |
} | |
private static boolean isLeftUpDiagonalWater(int row, int column, int[][] surface) { | |
if ((row == 0) || (column == 0)) { | |
return true; | |
} | |
return surface[row - 1][column - 1] == 0; | |
} | |
private static boolean isLeftDownDiagonalWater(int row, int column, int[][] surface) { | |
if ((row == surface.length - 1) || (column == 0)) { | |
return true; | |
} | |
return surface[row + 1][column - 1] == 0; | |
} | |
public static void main(String... args) { | |
test1(); | |
test2(); | |
test3(); | |
test4(); | |
} | |
/** | |
*/ | |
private static void test1() { | |
int[][] surface = {{}}; | |
System.out.println(numberOfIslands(surface)); // it should return 0 | |
} | |
/** | |
* 0 1 1 0 | |
* 0 0 0 0 | |
* 1 0 0 1 | |
*/ | |
private static void test2() { | |
int[][] surface = {{0, 1, 1, 0}, {0, 0, 0, 0}, {1, 0, 0, 1}}; | |
System.out.println(numberOfIslands(surface)); // it should return 3 | |
} | |
/** | |
* 0 1 1 0 0 0 1 | |
* 0 1 0 0 1 1 0 | |
* 0 1 1 0 0 1 0 | |
* 0 0 0 0 0 0 0 | |
* 0 1 1 1 1 1 0 | |
*/ | |
private static void test3() { | |
int[][] surface = { | |
{0, 1, 1, 0, 0, 0, 1}, | |
{0, 1, 0, 0, 1, 1, 0}, | |
{0, 1, 1, 0, 0, 1, 0}, | |
{0, 0, 0, 0, 0, 0, 0}, | |
{0, 1, 1, 1, 1, 1, 0}}; | |
System.out.println(numberOfIslands(surface)); // it should return 3 | |
} | |
/** | |
* 0 0 0 0 0 0 0 | |
* 0 0 0 0 1 0 0 | |
* 0 1 1 1 0 1 0 | |
* 0 0 0 0 0 0 0 | |
* 0 1 1 1 1 1 0 | |
*/ | |
private static void test4() { | |
int[][] surface = { | |
{0, 0, 0, 0, 0, 0, 0}, | |
{0, 0, 0, 0, 1, 0, 0}, | |
{0, 1, 1, 1, 0, 1, 0}, | |
{0, 0, 0, 0, 0, 0, 0}, | |
{0, 1, 1, 1, 1, 1, 0}}; | |
System.out.println(numberOfIslands(surface)); // it should return 2 | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment