2023华为OD机试 查找单入口空闲区域

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdbool.h>
using namespace std;
class SingleEntranceArea {
public:
    int dx[4] = { -1,0,1,0 };
    int dy[4] = { 0,1,0,-1 };
    int tmp_size = 0;
    vector<vector<int>> res;     // {x,y,size}    
    bool compare(vector<vector<int>> arr1, vector<vector<int>> arr2)
    {
        return arr1[0][2] > arr2[0][2];
    }
    void dfs(vector<vector<char>>& grid, int sx, int sy)
    {
        grid[sx][sy] = 'X';
        tmp_size++;
        for (int i = 0; i < 4; ++i)
        {
            int x = sx + dx[i];
            int y = sy + dy[i];
            if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == 'O')
            {
                if (x == 0 || x == grid.size() - 1 || y == 0 || y == grid[0].size() - 1)
                {
                    grid[x][y] = 'X';        // 封住入口
                    tmp_size = -1;
                    return;
                }
                dfs(grid, x, y);
            }
        }
    }
    void maxAreaOfIsland(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i)          // 遍历垂直方向
        {
            if (grid[i][0] == 'O')
            {
                dfs(grid, i, 0);
                if (tmp_size > 0) res.push_back({ i,0,tmp_size });
                tmp_size = 0;
            }
            if (grid[i][n - 1] == 'O')
            {
                dfs(grid, i, n - 1);
                if (tmp_size > 0) res.push_back({ i, n - 1 ,tmp_size });
                tmp_size = 0;
            }
        }
        for (int j = 0; j < n; ++j)          // 遍历水平方向
        {
            if (grid[0][j] == 'O') {
                dfs(grid, 0, j);
                if (tmp_size > 0) res.push_back({ 0,j,tmp_size });
                tmp_size = 0;
            }
            if (grid[m - 1][j] == 'O') {
                dfs(grid, m - 1, j);
                if (tmp_size > 0)res.push_back({ m - 1, j, tmp_size });
                tmp_size = 0;
            }
        }
        if (res.size() == 0) { cout << "NUL"; return; }
        else if (res.size() == 1) { cout << res[0][0] << " " << res[0][1] << " " << res[0][2]; return; }
        sort(this->res.begin(), this->res.end());
        if (res[0][2] == res[1][2]) cout << res[0][2];
        else cout << res[0][0] << " " << res[0][1] << " " << res[0][2];
    }
};
int main()
{
    vector<vector<char>> grid = {
        {'X','X','X','X'},
        {'X','X','O','O'},
        {'X','X','X','X'},
        {'X','X','O','O'},
        {'X','X','X','X'}
    };
    SingleEntranceArea sea;
    sea.maxAreaOfIsland(grid);
}