Number of Islands

1package pkg5leetcode;2 3/*4 * LeetCode 200: Number of Islands  (Medium)5 * -----------------------------------------6 * Count connected components of '1's in a grid (4-directional).7 *8 * APPROACH: scan the grid; on each unvisited '1', flood-fill (DFS) to sink the island.9 * COMPLEXITY: Time O(rows*cols), Space O(rows*cols) worst-case recursion.10 */11public class leetcode11NumberOfIslands {12 13    static int numIslands(char[][] grid) {14        if (grid == null || grid.length == 0) return 0;15        int count = 0;16        for (int r = 0; r < grid.length; r++)17            for (int c = 0; c < grid[0].length; c++)18                if (grid[r][c] == '1') { sink(grid, r, c); count++; }19        return count;20    }21 22    static void sink(char[][] g, int r, int c) {23        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;24        g[r][c] = '0';                          // mark visited25        sink(g, r + 1, c); sink(g, r - 1, c);26        sink(g, r, c + 1); sink(g, r, c - 1);27    }28 29    static char[][] grid(String... rows) {30        char[][] g = new char[rows.length][];31        for (int i = 0; i < rows.length; i++) g[i] = rows[i].toCharArray();32        return g;33    }34 35    public static void main(String[] args) {36        check(numIslands(grid("11110", "11010", "11000", "00000")) == 1, "one island");37        check(numIslands(grid("11000", "11000", "00100", "00011")) == 3, "three islands");38        check(numIslands(grid("000", "000")) == 0, "no island");39        System.out.println("leetcode11NumberOfIslands: all tests passed");40    }41 42    static void check(boolean cond, String name) {43        if (!cond) throw new AssertionError("FAILED: " + name);44        System.out.println("  PASS " + name);45    }46}