LeetCode200: 岛屿数量

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

示例 1:
输入:
11110
11010
11000
00000

输出: 1

示例 2:
输入:
11000
11000
00100
00011

输出: 3

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

解题思路：这里我运用了一个广度优先算法，用队列实现。

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;
                }
            }
        }
    }
}