給定一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，計(jì)算島嶼的數(shù)量。一個(gè)島被水包圍，并且它是通過(guò)水平方向或垂直方向上相鄰的陸地連接而成的。你可以假設(shè)網(wǎng)格的四個(gè)邊均被水包圍。

示例 1:
輸入:
11110
11010
11000
00000

輸出: 1

示例 2:
輸入:
11000
11000
00100
00011

輸出: 3

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

解題思路：這里我運(yùn)用了一個(gè)廣度優(yōu)先算法，用隊(duì)列實(shí)現(xiàn)。

package leetcode;

import java.util.LinkedList;
import java.util.Queue;

public class NumIslands {
    class Node {
        int x;
        int y;

        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static boolean[][] visited;
    static int count = 0;
    static int N;
    static int M;
    Queue<Node> queues = new LinkedList<>();

    public int numIslands(char[][] grid) {
        if (grid.length == 0) return 0;
        queues.clear();
        count = 0;
        N = grid.length;
        M = grid[0].length;
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if ((grid[i][j] == '1') && !visited[i][j]) {
                    queues.offer(new Node(i, j));
                    visited[i][j] = true;
                    bfs(grid);
                    count++;
                }
            }
        }
        return count;
    }

    private void bfs(char[][] grid) {
        while (queues.size() != 0) {
            Node tmp = queues.poll();
            int xTmp = tmp.x;
            int yTmp = tmp.y;
            for (int i = 0; i < 4; i++) {
                int xx = xTmp + dx[i];
                int yy = yTmp + dy[i];
                if (0 <= xx && xx < N && 0 <= yy && yy < M && grid[xx][yy] == '1' && !visited[xx][yy]) {
                    queues.offer(new Node(xx, yy));
                    visited[xx][yy] = true;
                }
            }
        }
    }
}