200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 示例 1:

  1. 输入:
  2. 11110
  3. 11010
  4. 11000
  5. 00000
  6. 输出: 1

示例 2:

  1. 输入:
  2. 11000
  3. 11000
  4. 00100
  5. 00011
  6. 输出: 3
  7. 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

解题思路
求连通图数量，可以用深度优先搜索和广度优先搜索遍历，能遍历完一个就算是一个连通图，遍历过程中注意把遍历过的标记一下，防止重复遍历。遍历完一个连通图后，下一次开始遍历的位置就是从没有被标记过的地方开始。

代码实现

  1. /*
  2.     求连通图数量，可以用深度优先搜索和广度优先搜索遍历，能遍历完一个就算是一个连通图
  3. */
  4. class Solution {
  5. public:
  6.     vector<vector<char>> graph;
  7.     int heng,zong;
  8.     void dep(int x,int y){
  9.         if(x>=heng || y>=zong || x<0 || y<0)
  10.             return;
  11.         if( graph[x][y] == '0' )
  12.             return;
  13.         graph[x][y] = '0' ;//标记为已经遍历过
  14.         dep(x,y-1);//往水平向左方向探查
  15.         dep(x,y+1);//往水平向右方向探查
  16.         dep(x+1,y);//往竖直向下方向探查
  17.         dep(x-1,y);//往竖直向上方向探查
  18.     }
  19.     int numIslands(vector<vector<char>>& grid) {
  20.         graph = grid;
  21.         heng = graph.size();
  22.         if(heng != 0)
  23.             zong = graph[0].size();
  24.         int num = 0;
  25.         for(int i = 0; i<heng;i++) {
  26.             for(int j=0;j<zong;j++) {
  27.                 if( graph[i][j] == '0' )
  28.                     continue;
  29.                 dep(i,j);
  30.                 num++;
  31.             }
  32.         }
  33.         return num;
  34.     }
  35. };