岛屿问题

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

示例 1:

输入:

11110
11010
11000
00000

输出: 1

示例 2:

输入:
11000
11000
00100
00011

输出: 3

java题解

class Solution {
    public int numIslands(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int num = 0;
        for(int i = 0; i<row; i++) {
            for (int j = 0; j<col; j++) {
                if(grid[i][j]=='1') {
                    grid[i][j] = 0;
                    num++;

                    LinkedList<Integer> queue = new LinkedList<Integer>();
                    int cur = (i*col+j);
                    queue.addLast(cur);
                    while (queue.size()!=0) {
                        int curr = queue.removeLast();
                        int curx = curr/col;
                        int cury = curr%col;
//
                        if ((curx-1)>=0 && (grid[curx-1][cury]=='1')){
                            grid[curx-1][cury] = 0;
                            queue.addLast((curx-1)*col+cury);
                        }if ((curx+1)<row && (grid[curx+1][cury]=='1')){
                            grid[curx+1][cury] = 0;
                            queue.addLast((curx+1)*col+cury);
                        }if ((cury-1)>=0 && (grid[curx][cury-1]=='1')){
                            grid[curx][cury-1] = 0;
                            queue.addLast((curx)*col+cury-1);
                        }if ((cury+1)<col && (grid[curx][cury+1]=='1')){
                            grid[curx][cury+1] = 0;
                            queue.addLast((curx)*col+cury+1);
                        }
                    }

                }
            }
        }
        return  num;
    }
}

广度优先。

从左上角开始，找到第一个值为 1 的位置，即找到第一个岛，将找到的位置放入队列并标记为已访问。

当队列不为空时，取出坐标位置，对该位置的上下左右方向的坐标进行判断，为陆地时加入队列并标记已访问。

当队列循环完毕时即该岛（连续陆地）已被全部标记。

再找到下一个值为 1 的坐标就是新的岛。