給你一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量。

島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。

此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。

示例 1：

輸入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
輸出：1

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-islands

解題思路

將二維矩陣看作圖，采用廣度優(yōu)先遍歷
掃描矩陣，遇到陸地則將其加入隊(duì)列，
當(dāng)隊(duì)列非空是，彈出隊(duì)首，然后以它為基礎(chǔ)將四個(gè)方向中為陸地的加入隊(duì)列
元素加入隊(duì)列時(shí)要將該元素設(shè)為"水"，防止重復(fù)遍歷
廣度優(yōu)先遍歷的次數(shù)就是島嶼數(shù)量

代碼

class Solution {
    int rows, cols;

    public int numIslands(char[][] grid) {
        rows = grid.length;
        cols = grid[0].length;
        int count = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    grid[i][j] = '0';
                    Deque<Integer> deque = new LinkedList<>();
                    deque.addLast(i * cols + j); // 二維坐標(biāo)轉(zhuǎn)為一維索引
                    while (!deque.isEmpty()) {
                        int index = deque.removeFirst();
                        int row = index / cols, col = index % cols;
                        helper(grid, row + 1, col, deque);
                        helper(grid, row - 1, col, deque);
                        helper(grid, row, col + 1, deque);
                        helper(grid, row, col - 1, deque);
                    }
                }
            }
        }
        return count;
    }

    private void helper(char[][] grid, int i, int j, Deque<Integer> deque) {
        if (i >= 0 && i < rows && j >= 0 && j < cols && grid[i][j] == '1') {
            grid[i][j] = '0';
            deque.addLast(i * cols + j);
        }
    }
}