背景：
给定一个网格

X X X X
X O O X
X X O X
X O X X

其中X表示陆地，O表示海洋

求：
1.leetcode 130 将被包围的海洋填成陆地
2.leetcode 200 求岛屿的数量
3.leetcode 695 求岛屿的最大面积
4.leetcode 1254 求被包围的海洋个数

思路总结：
1.如果涉及到被包围的‘O’的区域，此时要区分被包围的‘O’和未被包围的‘O’
1）遍历网格的边界，遇到‘O’就把它和它周围的‘O’污染；网格中剩下的‘O’是被包围的；
2）遍历整个网格，处理遍历到的‘O’

2.如果求‘O’区域的个数，省去1中第一步即可

模板：

void pollute(vector<vector<char>>& board,int i,int j){
        if(i>=0&&j>=0&&i<board.size()&&j<board[0].size()){
            if(board[i][j]=='O'){
                board[i][j]='S';
                pollute(board,i+1,j);
                pollute(board,i-1,j);
                pollute(board,i,j+1);
                pollute(board,i,j-1);
            }
        }
    }

1.leetcode 130 被包围的区域
C++代码：

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.empty()) return;
        int n=board.size(),m=board[0].size();

        for(int i=0;i<n;i++){
            int j=0;
            if(board[i][j]=='O') pollute(board,i,j);
            j=m-1;
            if(board[i][j]=='O') pollute(board,i,j);

        }

        for(int j=0;j<m;j++){
            int i=0;
            if(board[i][j]=='O') pollute(board,i,j);
            i=n-1;
            if(board[i][j]=='O') pollute(board,i,j);
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]=='S'){
                     board[i][j]='O';
                }
                else if(board[i][j]=='O') board[i][j]='X';
            }
        }
    }

    void pollute(vector<vector<char>>& board,int i,int j){
        if(i>=0&&j>=0&&i<board.size()&&j<board[0].size()){
            if(board[i][j]=='O'){
                board[i][j]='S';
                pollute(board,i+1,j);
                pollute(board,i-1,j);
                pollute(board,i,j+1);
                pollute(board,i,j-1);
            }
        }
    }
};

2.leetcode 200 岛屿数量

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;
        int res=0;
        int n=grid.size(),m=grid[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]=='1'){
                    pollute(grid,i,j);
                    res++;
                }
            }
        }
        return res;
    }

    void pollute(vector<vector<char>>& grid,int i,int j){
        if(i>=0&&i<grid.size()&&j>=0&&j<grid[0].size()){
            if(grid[i][j]=='1'){
                grid[i][j]='x';
                pollute(grid,i+1,j);
                pollute(grid,i-1,j);
                pollute(grid,i,j+1);
                pollute(grid,i,j-1);
            } 
        }
    }
};

3.leetcode 695 求岛屿的最大面积

class Solution {
public:
    int cnt=0;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int res=0;
        if(grid.empty()) return 0;
        int n=grid.size(),m=grid[0].size();

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cnt=0;
                if(grid[i][j]==1)
                    pollute(grid,i,j);
                res=max(res,cnt);
            }
        }

        return res;
    }

    void pollute(vector<vector<int>>& grid,int i,int j){
        if(i>=0&&j>=0&&i<grid.size()&&j<grid[0].size()){
            if(grid[i][j]==1){
                grid[i][j]=2;
                cnt++;
                pollute(grid,i+1,j);
                pollute(grid,i-1,j);
                pollute(grid,i,j+1);
                pollute(grid,i,j-1);
            }
        }
    }
};

4.leetcode 1254 求被包围的海洋个数

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int res=0;
        if(grid.empty()) return 0;
        int n=grid.size(),m=grid[0].size();

         for(int i=0;i<n;i++){
            int j=0;
            if(grid[i][j]==0) pollute(grid,i,j);
            j=m-1;
            if(grid[i][j]==0) pollute(grid,i,j);
         }

         for(int j=0;j<m;j++){
            int i=0;
            if(grid[i][j]==0) pollute(grid,i,j);
            i=n-1;
            if(grid[i][j]==0) pollute(grid,i,j);
         }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==0){
                    pollute(grid,i,j);
                    res++;
                }
            }
        }

        return res;
    }

    void pollute(vector<vector<int>>& grid,int i,int j){
        if(i>=0&&j>=0&&i<grid.size()&&j<grid[0].size()){
            if(grid[i][j]==0){
                grid[i][j]=2;
                pollute(grid,i+1,j);
                pollute(grid,i-1,j);
                pollute(grid,i,j+1);
                pollute(grid,i,j-1);
            }
        }
    }
};