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

BFS

// 首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点，然后对每个相邻的顶点再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束
// Time Complexity: O(m*n).  // m is the rows, and n is the cols;
// Space: O(m*n).

class Solution {
    public int numIslands(char[][] grid) {
        // corner case
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
           return 0; 
        }
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        int count = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    LinkedList<int []> queue = new LinkedList<int []>();
                    queue.add(new int[]{i, j});
                    while (!queue.isEmpty()) {
                        int[] cur = queue.poll();
                        for (int[] dir : dirs) {
                            int x = cur[0] + dir[0];
                            int y = cur[1] + dir[1];
                            if(x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == '1') {
                                grid[x][y] = '0';
                                queue.add(new int[]{x, y});
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
}

DFS

/*
若是碰到一个1, 用DFS把与它相连的1 都换成0. 继续扫描，最后算出能有多少个 单独的 1.
Time Complexity: O(m*n), m = grid.length, n = grid[0].length. 看起来像 O(m^2 * n^2), 对于每一个点 做DFS 用O(m*n). 一共m*n个点，其实每个点最多扫描两遍。
Space: O(m*n) 最多可以有O(m*n)层 stack. 
*/
// 5.21 DFS

class Solution {
    // Assumption
    final static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int numIslands(char[][] grid) {
        // corner case
        if(grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int count = 0;
        final int rows = grid.length;
        final int cols = grid[0].length;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if(grid[i][j] == '1') {
                    count++;
                    dfs (grid, i, j, rows, cols);
                }
            }
        }
        return count;
    }
    
    private void dfs(char[][] grid, int x, int y, int rows, int cols) {
        // base case
        if (x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] == '0') {
            return;
        }
        //recursive rule;
        grid[x][y] = '0';
        for (int[] dir : dirs) {
            int neiX = dir[0] + x;
            int neiY = dir[1] + y;
            dfs (grid, neiX, neiY, rows, cols);
        }
    }
}