200. 岛屿数量

给你一个由?'1'（陆地）和?'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j]?的值为?'0'?或?'1'

?

void run(vector<vector<char>>& grid,vector<vector<bool>>&visited,int i,int j)

? ? {

? ? ? ? if(i<0 || j<0)

? ? ? ? {

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? if(i>=grid.size() || j>=grid[0].size())

? ? ? ? {

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? if(true == visited[i][j])

? ? ? ? {

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? visited[i][j]=true;

? ? ? ? if(grid[i][j] == '0')

? ? ? ? {

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? //up

? ? ? ? run( grid,visited,i+1,j);

? ? ? ? run( grid,visited,i-1,j);

? ? ? ? run( grid,visited,i,j+1);

? ? ? ? run( grid,visited,i,j-1);

? ? }

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

? ? ? ? int row = grid.size();

? ? ? ? int col = grid[0].size();

? ? ? ? vector<vector<bool>>visited(row,vector<bool>(col,false));

? ? ? ? int ret=0;

? ? ? ? for(int i=0;i<row;i++)

? ? ? ? {

? ? ? ? ? ? for(int j=0;j<col;j++)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? if(grid[i][j] == '0' || true ==visited[i][j])

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? ? continue;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ret++;

? ? ? ? ? ? ? ? run( grid,visited,i,j);

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return ret;

? ? }