题目：

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input: 11000 11000 00100 00011 Output: 3

解题：

    ‘1’  未访问的位置， ‘v’ 访问的位置 ，’0′ 水面

深度优先：

    1. 对于标记为’1′ 的位置， 先标记为已访问’v’. 通过递归寻找及与其相关联上下左右的节点，如果标记为’1‘ 设置为已访问‘v’，找完并标记完所有关联的区域，返回true.

    3. 结束条件：标记为’0‘的节点或者已经越界的情况,  返回false.

实现：

bool visit(char **grid ,int maxrow, int maxcol, int x, int y  ){

    if (x>=maxrow || x< 0 || y>= maxcol|| y<0 ||grid[x][y]!='1'){
        return false;
    } 
    grid[x][y] = 'v';
    visit(grid, maxrow, maxcol, x-1, y);
    visit(grid, maxrow, maxcol, x+1, y);
    visit(grid, maxrow, maxcol, x, y-1);
    visit(grid, maxrow, maxcol, x, y+1);
    return true;
}


int numIslands(char** grid, int gridSize, int* gridColSize){
    
    int colnum = *gridColSize;
    int rownum = gridSize;
    int total = 0;
    
    if (grid == NULL){
        return 0;
    }
    for (int x=0; x<rownum; x++)
        for (int y=0; y<colnum; y++)
            total += visit(grid, rownum, colnum ,x,y)?1:0;
        
    return total;

}

时间复杂度O(N）

广度优先：

实现：

1. 借助queue，如果节点标为为‘1’，判断其上下左右节点，也为‘1’的标识为已访问’v‘ 再入queue， 之后出栈以下一层为中心遍历， 
2. 结束条件：该节点访问queue为空。 

class Solution {
public:
   int numIslands(vector<vector<char>>& grid) {
       int maxrow = grid.size();
       int maxcol  = maxrow ? grid[0].size():0;
       int offset[]={0,1,0,-1,0};
       int total=0;
        
       for (int row=0; row<maxrow; row++){
          for (int col=0; col<maxcol; col++){
               if (grid[row][col] == '1'){
                   total +=1;
                   grid[row][col] = 'v';
                   queue<pair<int,int>>  visit;
                   visit.push({row,col});
                   while (!visit.empty()){
                       pair<int, int> node = visit.front();
                       visit.pop();
                       for (int k=0; k<4; k++){
                             int row_v= node.first + offset[k];
                             int col_v = node.second + offset[k+1];
                             if (row_v >=0 && row_v <maxrow \
                                 && col_v  >=0 && col_v <maxcol \ 
                                 && grid[row_v][col_v]=='1' ){
                                        grid[row_v][col_v] = 'v';
                                        visit.push({row_v,col_v});
                            }
                       }//for k
                   }// while !viist
                }// if (grid[i][j] == '1')
            }// for j
        }// for i
        return total;
    }
};

参考：

4ms C DFS solution reusing grid to memoize visited squares

C++ BFS/DFS