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

示例 1:

输入:
11110
11010
11000
00000
输出: 1

示例 2:

输入:
11000
11000
00100
00011
输出: 3

思路分析：扫描整个矩阵，当我们的陆地（‘1’）时，就将与之相连的所以陆地标记，然后继续扫描。对于标记相邻的陆地，深度优先搜索、广度优先搜索都可以，这里只介绍广度优先搜索。

class Solution {
public:
	int numIslands(vector<vector<char>>& grid) {
		int resultCnt = 0;
		int rowSize = grid.size();
		if (rowSize == 0) {
			return 0;
		}
		int colSize = grid[0].size();
		if (colSize == 0) {
			return 0;
		}
        //遍历整个矩阵，如果发现岛屿，则将与其相连的陆地全部标记
		for (int row = 0; row < rowSize; ++row) {
			for (int col = 0; col < colSize; ++col) {
				if (grid[row][col] == '1') {
					resultCnt += 1;
					bfs(grid, row, col);//将这个岛屿标记
				}
			}
		}
		return resultCnt;
	}
    //用于将与grid[row][col]相邻的陆地全部标记为‘X’
	void bfs(vector<vector<char>>& grid, int row, int col) {
		int rowSize = grid.size(), colSize = grid[0].size();
		queue<int> myQue;//广度优先遍历辅助队列
		grid[row][col] = 'X';//标记
		myQue.push(row);
		myQue.push(col);
		while (!myQue.empty()) {
			row = myQue.front();
			myQue.pop();
			col = myQue.front();
			myQue.pop();
			if (row - 1 >= 0 && grid[row - 1][col] == '1') {//上方扩展
				grid[row - 1][col] = 'X';//标记
				myQue.push(row - 1);
				myQue.push(col);
			}
			if (row + 1 < rowSize && grid[row + 1][col] == '1') {//下方扩展
				grid[row + 1][col] = 'X';//标记
				myQue.push(row + 1);
				myQue.push(col);
			}
			if (col - 1 >= 0 && grid[row][col - 1] == '1') {//左方扩展
				grid[row][col - 1] = 'X';//标记
				myQue.push(row);
				myQue.push(col - 1);
			}
			if (col + 1 < colSize && grid[row][col + 1] == '1') {//右方扩展
				grid[row][col + 1] = 'X';//标记
				myQue.push(row);
				myQue.push(col + 1);
			}
		}
	}
};