当前位置：首页 > article >正文

查找单入口空闲区域[A卷-hw_od]

article 2025/3/29 0:03:33

查找单入口空闲区域[A卷 100分]

题目描述

给定一个 m x n 的矩阵，由若干字符 ‘X’ 和 ‘O’构成，’X’表示该处已被占据，’O’表示该处空闲，请找到最大的单入口空闲区域。

解释：

空闲区域是由连通的’O’组成的区域，位于边界的’O’可以构成入口，单入口空闲区域即有且只有一个位于边界的’O’作为入口的由连通的’O’组成的区域。如果两个元素在水平或垂直方向相邻，则称它们是“连通”的。

输入描述

第一行输入为两个数字，第一个数字为行数m，第二个数字为列数n，两个数字以空格分隔，1<=m,n<=200。

剩余各行为矩阵各行元素，元素为‘X’或‘O’，各元素间以空格分隔。

输出描述

若有唯一符合要求的最大单入口空闲区域，输出三个数字

第一个数字为入口行坐标（0~m-1）
第二个数字为入口列坐标（0~n-1）
第三个数字为区域大小

三个数字以空格分隔；若有多个符合要求，则输出区域大小最大的，若多个符合要求的单入口区域的区域大小相同，则此时只需要输出区域大小，不需要输出入口坐标。若没有，输出NULL。

用例1

输入:

4 4
X X X X
X O O X
X O O X
X O X X

输出:

3 1 5

说明:

存在最大单入口区域，入口坐标(3,1)，区域大小5

用例2

输入:

4 5
X X X X X
O O O O X
X O O O X
X O X X O

输出:

3 4 1

说明:

存在最大单入口区域，入口坐标（3,4），区域大小1

用例3

输入

5 4
X X X X
X O O O
X O O O
X O O X
X X X X

输出

NULL

说明

不存在最大单入口区域

用例4

输入

5 4
X X X X
X O O O
X X X X
X O O O
X X X X

输出

说明

存在两个大小为3的最大单入口区域，两个入口坐标分别为(1,3)、(3,3)

#include <bits/stdc++.h>
using namespace std;
struct Region {
    int ex, ey, size;
};
int m, n;
vector<vector<char>> grid;
vector<vector<bool>> visited;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int region_size;
int ex, ey;
int border_count;
void dfs(int x, int y) {
    visited[x][y] = true;
    region_size++;
    
    if (x == 0 || x == m-1 || y == 0 || y == n-1) {
        border_count++;
        ex = x;
        ey = y;
    }
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 'O' && !visited[nx][ny]) {
            dfs(nx, ny);
        }
    }
}
int main() {
    cin >> m >> n;
    grid.resize(m, vector<char>(n));
    visited.resize(m, vector<bool>(n, false));
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    
    vector<Region> regions;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if ((i == 0 || i == m-1 || j == 0 || j == n-1) && grid[i][j] == 'O' && !visited[i][j]) {
                region_size = 0;   //区域大小计数
                border_count = 0;  //边界计数
                ex = i;
                ey = j;
                
                dfs(i, j);
                
                if (border_count == 1) {
                    regions.push_back({ex, ey, region_size}); //符合条件1
                }
            }
        }
    }
    
    if (regions.empty()) {
        cout << "NULL" << endl;
        return 0;
    }
    
    int max_size = 0;
    for (const auto &r : regions) max_size = max(max_size, r.size);
    
    vector<Region> largest;
    for (const auto &r : regions) {
        if (r.size == max_size) largest.push_back(r);
    }
    
    if (largest.size() == 1) {
        cout << largest[0].ex << " " << largest[0].ey << " " << largest[0].size << endl;
    } else {
        cout << max_size << endl;
    }
    
    return 0;
}