LeetCode:岛屿数量

200. 岛屿数量

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

思路：当遇到 '1' 时，岛屿数量++，并对 '1' 的位置进行感染，把与该 '1' 位置直接或间接连通在一起的 '1' 全部标记为 '2'。然后继续遍历该二维网格。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0 || grid[0].size()==0)
            return 0;
        int row=grid.size(),col=grid[0].size();
        int res=0;
        for(int i=0;i<row;++i)
        {
            for(int j=0;j<col;++j)
            {
                if(grid[i][j]=='1')  //遇到 '1' 时，
                {
                    ++res;  //岛屿数量++
                    infect(grid,i,j,row,col); //对 '1' 的位置进行感染
                }
            }
        }
        return res;
    }

    void infect(vector<vector<char>>& grid,int i, int j,const int &row, const int&col)
    {
        if(i<0 || i>=row || j<0 || j>=col || grid[i][j] != '1') //越界或不为 '1' ，返回
        {
            return;
        }
        grid[i][j]='2';  //把与该 '1' 位置直接或间接连通在一起的 '1' 全部标记为 '2'
        infect(grid,i-1,j,row,col);
        infect(grid,i+1,j,row,col);
        infect(grid,i,j-1,row,col);
        infect(grid,i,j+1,row,col);
    }
};