https://leetcode.cn/problems/max-area-of-island/
//https://leetcode.cn/problems/max-area-of-island/
//岛屿的最大面积
// 解法一：bfs
// class Solution {
// public:
//     int dx[4] = {1,-1,0,0};
//     int dy[4] = {0,0,1,-1};
//     int maxAreaOfIsland(vector<vector<int>>& grid) {
//         int m = grid.size();
//         int n = grid[0].size();
//         int max_area = 0;
//         queue<pair<int,int>> q;
//         for(int r = 0; r < m; ++r)
//         {
//             for(int c = 0; c < n; ++c)
//             {
//                 if(grid[r][c] == 1)
//                 {
//                     int area = 0;
//                     area += 1;
//                     grid[r][c] = 0;
//                     q.push({r,c});
//                     while(q.size())
//                     {
//                         auto [a,b] = q.front();
//                         q.pop();
//                         //area += 1;   //对数据的处理不要放在这里
//                         //grid[a][b] = 0;
//                         for(int i = 0; i < 4; ++i)
//                         {
//                             int x = a+dx[i], y = b+dy[i];
//                             if(x >= 0 && x < m && y >= 0 && y < n && 1 == grid[x][y])
//                             {
//                                 q.push({x,y});
//                                 area += 1;
//                                 grid[x][y] = 0;
//                             }
//                         }
//                     }
//                     if(area > max_area)
//                         max_area = area;
//                 }
//             }
//         }
//         return max_area;
//     }
// };

// 还是解法一：bfs
// 封装成函数
// class Solution {
// public:
//     int dx[4] = {1,-1,0,0};
//     int dy[4] = {0,0,1,-1};
//     int maxAreaOfIsland(vector<vector<int>>& grid) {
//         int m = grid.size();
//         int n = grid[0].size();
//         int max_area = 0;
//         for(int r = 0; r < m; ++r)
//         {
//             for(int c = 0; c < n; ++c)
//             {
//                 if(grid[r][c] == 1)
//                 {
//                     int area = bfs(grid,r,c);
//                     if(area > max_area)
//                         max_area = area;
//                 }
//             }
//         }
//         return max_area;
//     }
//     int bfs(vector<vector<int>>& grid, int r, int c)
//     {
//         int m = grid.size();
//         int n = grid[0].size();
//         int area = 0;
//         queue<pair<int,int>> q;
//         q.push({r,c});
//         area += 1;
//         grid[r][c] = 0;
//         while(q.size())
//         {
//             auto [a,b] = q.front();
//             q.pop();
//             //area += 1;   //对数据的处理不要放在这里
//             //grid[a][b] = 0;
//             for(int i = 0; i < 4; ++i)
//             {
//                 int x = a+dx[i], y = b+dy[i];
//                 if(x >= 0 && x < m && y >= 0 && y < n && 1 == grid[x][y])
//                 {
//                     q.push({x,y});
//                     area += 1;
//                     grid[x][y] = 0;
//                 }
//             }
//         }
//         return area;
//     }
// };

// 解法二：dfs
class Solution {
public:
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    int m,n;

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ret = 0;
        m = grid.size();
        n = grid[0].size();
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == 1)
                {
                    int num = 0;
                    dfs(grid,i,j,num);
                    ret = max(ret,num);
                }
            } 
        }
        return ret;    
    }

    void dfs(vector<vector<int>>& grid, int i, int j, int& num)
    {
        num++;
        grid[i][j] = 0;
        for(int k = 0; k < 4; ++k)
        {
            int x = i+dx[k];
            int y = j+dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1)
            {
                grid[x][y] = 0;
                dfs(grid,x,y,num);
            }
        }
    }
};
--------------------------------------------------------------------------------------------------
https://leetcode.cn/problems/surrounded-regions/
// 解法一：bfs
// https://leetcode.cn/problems/surrounded-regions/
// 被围绕的区域
// class Solution {
// public:
//     int dx[4] = {1,-1,0,0};
//     int dy[4] = {0,0,-1,1};
//     int m = 0;
//     int n = 0;

//     void solve(vector<vector<char>>& board) {
//         m = board.size();
//         n = board[0].size();
//         for(int r = 0; r < m; ++r)
//         {
//             for(int c = 0; c < n; ++c)
//             {
//                 if(r != 0 && r != m-1 && c != 0 && c != n-1 && board[r][c] == 'O')
//                 {
//                     //广度优先搜索判断是否可以修改
//                     int flag = bfs_p(board,r,c);
//                     if(flag)
//                     {
//                         //修改
//                         bfs_d(board, r, c);
//                     }
//                 }
//             }
//         }
//     }

//     int bfs_p(vector<vector<char>> board, int r, int c)
//     {
//         int flag = 1;
//         queue<pair<int,int>> q;
//         q.push({r,c});
//         board[r][c] = 'X';
//         while(q.size())
//         {
//             auto [a,b] = q.front();
//             q.pop();

//             for(int i = 0; i < 4; ++i)
//             {
//                 int x = a+dx[i], y = b+dy[i];
//                 if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
//                 {
//                     q.push({x,y});
//                     board[x][y] = 'X';
//                     if(x == 0 || x== m-1 || y == 0 || y == n-1)
//                     {
//                         flag = 0;
//                         return flag;
//                     }
//                 }
//             }
//         }

//         return flag;
//     }

//     void bfs_d(vector<vector<char>>& board, int r, int c)
//     {
//         queue<pair<int,int>> q;
//         q.push({r,c});
//         board[r][c] = 'X';
//         while(q.size())
//         {
//             auto [a,b] = q.front();
//             q.pop();
            
//             for(int i = 0; i < 4; ++i)
//             {
//                 int x = a+dx[i], y = b+dy[i];
//                 if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
//                 {
//                     q.push({x,y});
//                     board[x][y] = 'X';
//                 }
//             }
//         }
//     }
// };

// class Solution {
// public:
//     int dx[4] = {1,-1,0,0};
//     int dy[4] = {0,0,-1,1};
//     int m = 0;
//     int n = 0;

//     void solve(vector<vector<char>>& board) {
//         m = board.size();
//         n = board[0].size();

//         for(int y = 0; y < n; ++y)
//         {
//             if(board[0][y] == 'O') bfs_a(board, 0, y);
//             if(board[m-1][y] == 'O') bfs_a(board, m-1, y);
//         }
//         for(int x = 0; x < m; ++x)
//         {
//             if(board[x][0] == 'O') bfs_a(board, x, 0);
//             if(board[x][n-1] == 'O') bfs_a(board, x, n-1);
//         }

//         for(int r = 1; r < m; ++r)
//             for(int c = 1; c < n; ++c)
//                 if(board[r][c] == 'O') bfs_X(board,r,c);

//         for(int r = 0; r < m; ++r)
//             for(int c = 0; c < n; ++c)
//                 if(board[r][c] == 'a') bfs_O(board,r,c);
//     }

//     void bfs_O(vector<vector<char>>& board,int x,int y)
//     {
//         queue<pair<int,int>> q;
//         q.push({x,y});
//         board[x][y] = 'O';
//         while(q.size())
//         {
//             auto [a,b] = q.front();
//             q.pop();
//             for(int i = 0; i < 4; ++i)
//             {
//                 int x = a+dx[i];
//                 int y = b+dy[i];
//                 if(x >=0 && x < m && y >=0 && y < n && board[x][y] == 'a')
//                 {
//                     q.push({x,y});
//                     board[x][y] = 'O';
//                 }
//             }
//         }
//     }

//     void bfs_X(vector<vector<char>>& board,int x,int y)
//     {
//         queue<pair<int,int>> q;
//         q.push({x,y});
//         board[x][y] = 'X';
//         while(q.size())
//         {
//             auto [a,b] = q.front();
//             q.pop();
//             for(int i = 0; i < 4; ++i)
//             {
//                 int x = a+dx[i];
//                 int y = b+dy[i];
//                 if(x >=0 && x < m && y >=0 && y < n && board[x][y] == 'O')
//                 {
//                     q.push({x,y});
//                     board[x][y] = 'X';
//                 }
//             }
//         }
//     }

//     void bfs_a(vector<vector<char>>& board,int x,int y)
//     {
//         queue<pair<int,int>> q;
//         q.push({x,y});
//         board[x][y] = 'a';
//         while(q.size())
//         {
//             auto [a,b] = q.front();
//             q.pop();
//             for(int i = 0; i < 4; ++i)
//             {
//                 int x = a+dx[i];
//                 int y = b+dy[i];
//                 if(x >=0 && x < m && y >=0 && y < n && board[x][y] == 'O')
//                 {
//                     q.push({x,y});
//                     board[x][y] = 'a';
//                 }
//             }
//         }
//     }
// };

// class Solution {
// public:
//     int dx[4] = {1,-1,0,0};
//     int dy[4] = {0,0,-1,1};
//     int m = 0;
//     int n = 0;
//     void solve(vector<vector<char>>& board) {
//         m = board.size();
//         n = board[0].size();
//         for(int y = 0; y < n; ++y)
//         {
//             if(board[0][y] == 'O') bfs_a(board, 0, y);
//             if(board[m-1][y] == 'O') bfs_a(board, m-1, y);
//         }
//         for(int x = 0; x < m; ++x)
//         {
//             if(board[x][0] == 'O') bfs_a(board, x, 0);
//             if(board[x][n-1] == 'O') bfs_a(board, x, n-1);
//         }
//         for(int r = 0; r < m; ++r)
//             for(int c = 0; c < n; ++c)
//                 if(board[r][c] == 'O') board[r][c] = 'X';
//                 else if(board[r][c] == 'a') board[r][c] = 'O';
//     }
//     void bfs_a(vector<vector<char>>& board,int x,int y)
//     {
//         queue<pair<int,int>> q;
//         q.push({x,y});
//         board[x][y] = 'a';
//         while(q.size())
//         {
//             auto [a,b] = q.front();
//             q.pop();
//             for(int i = 0; i < 4; ++i)
//             {
//                 int x = a+dx[i];
//                 int y = b+dy[i];
//                 if(x >=0 && x < m && y >=0 && y < n && board[x][y] == 'O')
//                 {
//                     q.push({x,y});
//                     board[x][y] = 'a';
//                 }
//             }
//         }
//     }
// };

// 解法二：dfs
class Solution {
public:
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,-1,1};
    int m = 0;
    int n = 0;
    bool check[300][300];

    void solve(vector<vector<char>>& board) {
        m = board.size();
        n = board[0].size();
        for(int col = 0; col < n; ++col)
        {
            if(board[0][col] == 'O')
            {
                dfs(board,0,col);
            }
            if(board[m-1][col] == 'O')
            {
                dfs(board,m-1,col);
            }
        }

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

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

    void dfs(vector<vector<char>>& board, int i, int j)
    {
        check[i][j] = true;
        for(int k = 0; k < 4; ++k)
        {
            int x = i+dx[k];
            int y = j+dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && board[x][y] == 'O')
            {
                dfs(board,x,y);
            }
        }
    }
};