Number of Islands

1package pkg5leetcode.blind75;2 3/*4 * Number of Islands | LC 2005 * APPROACH: DFS flood-fill each unvisited '1' land cell.6 * COMPLEXITY: Time O(mn), Space O(mn) recursion7 */8public class blind75_LC200NumberOfIslands {9    static int numIslands(char[][] grid) {10        int count = 0;11        for (int i = 0; i < grid.length; i++)12            for (int j = 0; j < grid[0].length; j++)13                if (grid[i][j] == '1') { dfs(grid, i, j); count++; }14        return count;15    }16 17    static void dfs(char[][] g, int r, int c) {18        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;19        g[r][c] = '0';20        dfs(g, r + 1, c); dfs(g, r - 1, c); dfs(g, r, c + 1); dfs(g, r, c - 1);21    }22 23    public static void main(String[] args) {24        check(numIslands(new char[][]{{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}}) == 1, "case1");25        check(numIslands(new char[][]{{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}}) == 3, "case2");26        System.out.println("all tests passed");27    }28 29    static void check(boolean cond, String name) {30        if (!cond) throw new AssertionError("FAILED: " + name);31        System.out.println("  PASS " + name);32    }33}