原题

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例1:

输入:
11110
11010
11000
00000

输出: 1

示例2:

输入:
11000
11000
00100
00011

输出: 3

解法

思想

线性扫描整个二维网格，如果一个结点包含 1，则以其为根结点启动广度优先搜索，或深度优先搜索。搜索到的值设为 0 以标记访问过该结点，每经历过一次搜索说明岛的数量+1。直到整个二维数组都变成0。

代码

不嫌麻烦的可以建一个存储二维数组x、y位置的数据结构类。不然只能存储元素的偏移地址手动算x和y。

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        int height = grid.length;
        if(height==0) return 0;
        int width = grid[0].length;
        Queue<Integer> queue = new LinkedList<Integer>();

        for(int i = 0;i<height;i++){
            for(int j = 0;j<width;j++){
                if(grid[i][j]=='1'){
                    grid[i][j] = '0';
                    queue.offer(i*width+j);
                    while(!queue.isEmpty()){
                        int index = queue.poll();
                        int index_x = index/width;
                        int index_y = index%width;
                        if(index_x!=height-1 && grid[index_x+1][index_y]=='1'){ 
                            queue.offer((index_x+1)*width+index_y);
                            grid[index_x+1][index_y] = '0';
                        }
                        if(index_x!=0 && grid[index_x-1][index_y]=='1'){ 
                            queue.offer((index_x-1)*width+index_y);
                            grid[index_x-1][index_y] = '0';
                        }
                        if(index_y!=0 && grid[index_x][index_y-1]=='1'){ 
                            queue.offer(index_x*width+index_y-1);
                            grid[index_x][index_y-1] = '0';
                        }
                        if(index_y!=width-1 && grid[index_x][index_y+1]=='1'){ 
                            queue.offer(index_x*width+index_y+1);
                            grid[index_x][index_y+1] = '0';
                        }
                    }
                    count++;
                }
            }
        }
        return count;
    }
}

在BFS的基础上改一下就成了DFS：

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        int height = grid.length;
        if(height==0) return 0;
        int width = grid[0].length;
        Stack<Integer> stack = new Stack<>();

        for(int i = 0;i<height;i++){
            for(int j = 0;j<width;j++){
                if(grid[i][j]=='1'){
                    grid[i][j] = '0';
                    stack.push(i*width+j);
                    while(!stack.empty()){
                        int index = stack.peek();
                        int index_x = index/width;
                        int index_y = index%width;
                        if(index_x!=height-1 && grid[index_x+1][index_y]=='1'){ 
                            stack.push((index_x+1)*width+index_y);
                            grid[index_x+1][index_y] = '0';
                            continue;
                        }
                        if(index_x!=0 && grid[index_x-1][index_y]=='1'){ 
                            stack.push((index_x-1)*width+index_y);
                            grid[index_x-1][index_y] = '0';
                            continue;
                        }
                        if(index_y!=0 && grid[index_x][index_y-1]=='1'){ 
                            stack.push(index_x*width+index_y-1);
                            grid[index_x][index_y-1] = '0';
                            continue;
                        }
                        if(index_y!=width-1 && grid[index_x][index_y+1]=='1'){ 
                            stack.push(index_x*width+index_y+1);
                            grid[index_x][index_y+1] = '0';
                            continue;
                        }else{
                            stack.pop();
                        }
                    }
                    count++;
                }
            }
        }
        return count;
    }
}

当然DFS还可以用递归的系统调用栈：（作者：LeetCode）

class Solution {
  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);
  }

  public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
      return 0;
    }

    int nr = grid.length;
    int nc = grid[0].length;
    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }

    return num_islands;
  }
}