Title: Number of Islands Source: leetcode.com
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
|
1 2 3 4 |
11110 11010 11000 00000 |
Answer: 1
Example 2:
|
1 2 3 4 |
11000 11000 00100 00011 |
Answer: 3
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
/*https://leetcode.com/problems/number-of-islands/*/ import java.util.HashSet; public class NumberOfIslands { public static void main(String args[]) { char[][] grid = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}}; NumberOfIslands n = new NumberOfIslands(); System.out.println(n.numIslands(grid)); grid = new char[][]{{'1', '1', '0', '0', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '1', '0', '0'}, {'0', '0', '0', '1', '1'}}; System.out.println(n.numIslands(grid)); grid = new char[][]{{'1', '1', '1'}, {'0', '1', '0'}, {'1', '1', '1'}}; System.out.println(n.numIslands(grid)); } public int numIslands(char[][] grid) { HashSet<Pair<Integer, Integer>> global = new HashSet<Pair<Integer, Integer>>(); int count = 0; for(int i=0;i<grid.length;i++) { for(int j=0;j<grid[i].length;j++) { Pair<Integer, Integer> pair = new Pair<Integer, Integer>(i,j); if(!global.contains(pair) && grid[i][j]!='0') { findComponents(i, j, global, grid); count++; } } } return count; } public void findComponents(int row, int col, HashSet<Pair<Integer,Integer>> global, char[][] grid) { if(row<grid.length && row > -1 && col<grid[0].length && col > -1 && grid[row][col]=='1' && !global.contains(new Pair<Integer, Integer>(row, col))) { global.add(new Pair<Integer, Integer>(row, col)); findComponents(row-1, col, global, grid); findComponents(row+1, col, global, grid); findComponents(row, col-1, global, grid); findComponents(row, col+1, global, grid); } return; } } class Pair<L,R> { public final L left; public final R right; public Pair(L left, R right) { this.left = left; this.right = right; } public L getLeft() { return this.left; } public R getRight() { return this.right; } @Override public String toString() { return "Pair [left=" + this.left + ", right=" + this.right + "]"; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((this.left == null) ? 0 : this.left.hashCode()); result = prime * result + ((this.right == null) ? 0 : this.right.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } @SuppressWarnings("rawtypes") Pair other = (Pair) obj; if (this.left == null) { if (other.left != null) { return false; } } else if (!this.left.equals(other.left)) { return false; } if (this.right == null) { if (other.right != null) { return false; } } else if (!this.right.equals(other.right)) { return false; } return true; } } |