Question
Formatted question description: https://leetcode.ca/all/200.html
200 Number of Islands
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:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
Algorithm
Need to use DFS to solve, create a visited array to record whether a certain location has been visited.
For a location that is ‘1’ and has not been visited, recursively enter the number of ‘1’ in its up, down, left, and right positions, assign its visited corresponding value to true, and continue to enter all its adjacent neighbors, so that this Find all the numbers in the connected area, and assign true to the value in the visited.
After finding the adjacent area, increment the result by 1, and then continue to find the next position that is ‘1’ and has not been visited, and so on until the entire original array is traversed.
Or, skipping the visited array to record, just set all visited ‘1’ to be ‘0’. (Assuming we can alter the original array)
grid[i][j] = '0';
Code
Java
public class Number_of_Islands {
public static void main (String[] args) {
Number_of_Islands out = new Number_of_Islands();
Solution s = out.new Solution();
System.out.println(s.numIslands(new char[][]{ {'1', '1', '0', '0', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '1', '0', '0'}, {'0', '0', '0', '1', '1'} }));
}
// from online, directly overrite visited 1s
public class Solution {
private int n;
private int m;
public int numIslands(char[][] grid) {
int count = 0;
n = grid.length;
if (n == 0) return 0;
m = grid[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
if (grid[i][j] == '1') {
dfs(grid, i, j);
++count;
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
// @note: grid[i][j] != '1', should last of if(), or else index out of boundary
if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] != '1') {
return;
}
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}
class Solution_bfs {
public int numIslands(char[][] grid) {
int h = grid.length; // height
if (h == 0)
return 0;
int w = grid[0].length; // width
int count = 0;
boolean[][] visited = new boolean[h][w];
Queue<Integer[]> queue = new LinkedList<>();
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
queue.add(new Integer[]{i, j});
BFS(queue, grid, visited);
count++;
}
}
}
return count;
}
private void BFS(Queue<Integer[]> queue, char[][] islandGrid, boolean[][] visited) {
int H = islandGrid.length;
int L = islandGrid[0].length;
while (!queue.isEmpty()) {
Integer[] x = queue.remove();
int row = x[0];
int col = x[1];
if (row < 0 || col < 0 || row >= H || col >= L || visited[row][col] || islandGrid[row][col] != '1')
continue;
visited[row][col] = true;
queue.add(new Integer[]{row, (col - 1)});
queue.add(new Integer[]{row, (col + 1)});
queue.add(new Integer[]{(row - 1), col});
queue.add(new Integer[]{(row + 1), col});
}
}
}
// union find
class Solution_uf {
final int d[][] = { // direction
{0, 1},
{1, 0},
{0, -1},
{-1, 0}
};
public int numIslands(char[][] grid) {
int h = grid.length;
if (h == 0)
return 0;
int w = grid[0].length;
int N = 0; // id for each point, prepare for UF
List<Point> ptlist = new ArrayList<Point>(); // each position, Point list
Map<String, Integer> map = new HashMap<String, Integer>(); // (i,j) => count
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (grid[i][j] == '1') {
Point pt = new Point(i,j);
ptlist.add(pt);
map.put(i+","+j, N++);
}
}
}
UF uf = new UF(N);
for (int i = 0; i < N; i++) {
Point curr = ptlist.get(i);
int row = curr.x;
int col = curr.y;
for (int k = 0; k < 4; k++) {
int x = row + d[k][0];
int y = col + d[k][1];
if (isValid(grid, h, w, x, y)) {
uf.union(i, map.get(x + "," + y));
}
}
}
return uf.count();
}
private boolean isValid(char[][] grid, int width, int height, int row, int col) {
return (row >= 0) && (row < width) && (col >= 0) && (col < height) && grid[row][col] == '1';
}
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
class UF {
private int[] parent;
private byte[] rank;
private int count;
public UF(int n) {
if (n < 0) throw new IllegalArgumentException();
count = n;
parent = new int[n];
rank = new byte[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int p) {
validate(p);
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public int count() {
return count;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
else {
parent[rootQ] = rootP;
rank[rootP]++;
}
count--;
}
private void validate(int p) {
int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
}
}
}
}