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:

Input:

11110
11010
11000
00000


Output:
 1

Example 2:

Input:

11000
11000
00100
00011


Output: 
3

Solution

(1) Java

class Solution {
    class UF {
        int[] parents = null;
        int[] ranks = null;
        int count = 0;

        public UF(char[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            parents = new int[m*n];
            ranks = new int[m*n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        count++;
                        parents[i*n+j] = i*n+j;
                    }
                }
            }
        }

        public int find(int i) {
            if (parents[i] != i) {
                parents[i] = find(parents[i]);
            }
            return parents[i];
        }

        public void union(int i, int j) {
            int rooti = find(i);
            int rootj = find(j);
            if (rooti != rootj) {
                if (ranks[i] >= ranks[j]) {
                    parents[rootj] = rooti;
                    ranks[rooti]++;
                } else if (ranks[i] < ranks[j]) {
                    parents[rooti] = rootj;
                    ranks[rootj]++;
                } 
                count--;
            }
        }

        public int getCount() {
            return count;
        }
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        UF uf = new UF(grid);
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    if (i-1 >= 0 && grid[i-1][j] == '1') {
                        uf.union(i*n+j, (i-1)*n+j);
                    }
                    if (i+1 < m && grid[i+1][j] == '1') {
                        uf.union(i*n+j, (i+1)*n+j);
                    }
                    if (j-1 >= 0 && grid[i][j-1] == '1') {
                        uf.union(i*n+j, i*n+j-1);
                    }
                    if (j+1 < n && grid[i][j+1] == '1') {
                        uf.union(i*n+j, i*n+j+1);
                    }
                }
            }
        }
        return uf.getCount();
    }
}

(2) Python

class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        def update(i, j):
            if i < 0 or i >= m or j < 0 or j >= n:
                return
            if grid[i][j] == '0':
                return
            grid[i][j] = '0'
            update(i-1, j)
            update(i+1, j)
            update(i, j-1)
            update(i, j+1)

        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        rst = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    rst += 1
                    update(i, j)
        return rst

(3) Scala