Number of Islands

• 对每个需要的点进行BFS，理解每个BFS的结果是visit所有与这个点相邻的有效点，即找到了这个岛，
• 理解在运用BFS里需要存的对象应该是坐标组，而不是单纯的char值，which has no meaning, to do this, 3 ways
  1. new Coordinate class
  2. new int[]{x,y}
  3. serialize (x,y) to x*col + y, and then deserialize back
• 对于visit过的点进行标记，避免重复计算（这里吧grid的值改为0或者'v'） 这里在加入Queue的时候标记，而不是在poll的时候，不然就仍然有大量重复计算
• 复杂度都为O(mn)

Solution

public int numIslands(char[][] grid) {
        int total = 0;
        if (grid.length == 0 || grid[0].length == 0) return total;
        int row = grid.length;
        int col = grid[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    total++;
                }
            }
        }
        return total;
    }
    public void bfs (char[][] grid, int x, int y) {
        Queue<Integer> queue = new LinkedList<>(); 
        int col = grid[0].length;
        queue.offer(x * col + y);
        grid[x][y] = 'v';
        int[] deltaX = {0, 1, -1, 0};
        int[] deltaY = {1, 0, 0, -1};
        while (!queue.isEmpty()) {
            int top = queue.poll();
            //check the nearby nodes
            for (int i = 0; i < 4; i++) {
                int newX = top / col + deltaX[i];
                int newY = top % col + deltaY[i];
                if (validPosition(newX, newY, grid) && grid[newX][newY] == '1' ) {
                    queue.offer(newX * col + newY);
                    grid[newX][newY] = 'v';
                }
            }
        }
        return;
    }
    public boolean validPosition(int x, int y, char[][] grid) {
        if (x >= 0 && x < grid.length && y >=0 && y < grid[0].length)
            return true;
        return false;
    }


    //DFS
      void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
          return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
      }