题解 | #岛屿数量#

解题思路：

访问节点，如果该节点是1，那么将岛屿数量加一，同时将与它相临的1找出来，mark为0，因为这么多相邻的1只算一个岛屿

而第二步将相邻的1找出来mark为0有两种办法： 深度优先（depth first search)和广度优先（breadth-first-search）

具体实现1 dfs:

import java.util.*;


public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组
     * @return int整型
     */

    public int solve (char[][] grid) {

        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int count = 0;
        for (int row = 0; row < grid.length; row ++) {
            for (int column = 0; column < grid[0].length; column ++) {
                if (grid[row][column] == '1') {
                    count += 1;
                    dfsMarkNeighborAsZero(grid, row, column);
                }
            }
        }
        return count;
    }

    private void dfsMarkNeighborAsZero(char[][] grid, int row, int column) {
        if (isOutOfBoundary(grid, row, column) || grid[row][column] == '0')  {
            return;
        }

        grid[row][column] = '0';
        dfsMarkNeighborAsZero(grid, row - 1, column);
        dfsMarkNeighborAsZero(grid, row + 1, column);
        dfsMarkNeighborAsZero(grid, row, column - 1 );
        dfsMarkNeighborAsZero(grid, row, column + 1 );
    }

    private boolean isOutOfBoundary(char[][]grid, int row, int column) {
        return row < 0 || row > grid.length - 1 || column < 0 ||
               column > grid[0].length - 1;
    }
}

具体实现2 bfs:

import java.util.*;


public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组
     * @return int整型
     */

    public int solve (char[][] grid) {

        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int count = 0;
        Queue<Integer> xPosition = new LinkedList<Integer>();
        Queue<Integer> yPosition = new LinkedList<Integer>();
        for (int row = 0; row < grid.length; row ++) {
            for (int column = 0; column < grid[0].length; column ++) {
                if (grid[row][column] == '1') {
                    count += 1;
                    xPosition.add(row);
                    yPosition.add(column);
                    bfsMarkNeighborAsZero(grid, xPosition, yPosition);
                }
            }
        }
        return count;
    }

    private void bfsMarkNeighborAsZero(char[][] grid, Queue<Integer> xPosition,
                                       Queue<Integer> yPosition) {
        while (!xPosition.isEmpty()) {
            int row = xPosition.poll();
            int column = yPosition.poll();
            if (isOutOfBoundary(grid, row, column) || grid[row][column] == '0')  {
                continue;
            }
            grid[row][column] = '0';

            if (!isOutOfBoundary(grid, row + 1, column) && grid[row + 1][column] != '0') {
                xPosition.add(row + 1);
                yPosition.add(column);
            }

            if (!isOutOfBoundary(grid, row - 1, column) && grid[row - 1][column] != '0') {
                xPosition.add(row - 1);
                yPosition.add(column);
            }

            if (!isOutOfBoundary(grid, row, column - 1) && grid[row][column - 1] != '0') {
                xPosition.add(row);
                yPosition.add(column - 1) ;
            }

            if (!isOutOfBoundary(grid, row, column + 1) && grid[row][column + 1] != '0') {
                xPosition.add(row);
                yPosition.add(column + 1) ;
            }
        }
    }

    private boolean isOutOfBoundary(char[][]grid, int row, int column) {
        return row < 0 || row > grid.length - 1 || column < 0 ||
               column > grid[0].length - 1;
    }
}

BFS借助两个队列，一个存储行的坐标，一个存储列的坐标

每次遇到数值为1的情况，都将它的行坐标和列坐标分别入队

这个数值入队之后，要用BFS将和它相临的所有的1置为0

在while循环内先取出队头元素，

如果它的值不是1，或者它不在范围内就不用处理，否则将它置为0；

然后将它周围的所有值为1的节点都加入队

循环直至处理了所有的元素

每跑完一次while，一个岛屿的1都被置为0了。