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

示例 1:

输入: 11110 11010 11000 00000 输出: 1

示例 2:

输入: 11000 11000 00100 00011 输出: 3

广度优先搜索

class Solution {

public:

    int dx[4] = {1, -1, 0, 0};

    int dy[4] = {0, 0, 1, -1};

    int numIslands(vector<vector<char> >& grid)

    {

        int r = grid.size();

        if(r == 0)

        {

            return 0;

        }

        int c = grid[0].size();

        vector<vector<bool> > visit(r, vector<bool>(c, false));

        queue<pair<int, int> > q;

        int res = 0;

        for(int i = 0; i < r; i++)

        {

            for(int j = 0; j < c; j++)

            {

                if(grid[i][j] == '1' && visit[i][j] == false)

                {

                    res++;

                    visit[i][j] = true;

                    q.push(make_pair(i ,j));

                    while(!q.empty())

                    {

                        int x = q.front().first;

                        int y = q.front().second;

                        q.pop();

                        for(int i = 0; i < 4; i++)

                        {

                            int xx = x + dx[i];

                            int yy = y + dy[i];

                            if(xx < 0 || xx >= r || yy < 0 || yy >= c)

                                continue;

                            if(visit[xx][yy] == true || grid[xx][yy] == '0')

                                continue;

                            visit[xx][yy] = true;

                            q.push(make_pair(xx, yy));

                        }

                    }

                }

            }

        }

        return res;

    }

};