查找单入口空闲区域

题目描述

给定一个 m * n的矩阵，由若干字符' X' 和'0'构成，"X表示该处已被占据，'0"表示该处空闲，请找到最大的单入口空闲区域。解释:空闲区域是由连通的'0"组成的区域，位于边界的"0'可以构成入口，单入口空闲区域即有且只有一个位于边界的"0"作为入口的由连通的'O'组成的区域。如果两个元素在水平或垂直方向相邻，则称它们是“连通”的。

输入描述

第一行输入为两个数字，第一个数字为行数m，第二个数字列数n，两个数字以空格分隔，1<=m,n<=200.剩余各行为矩阵各行元素，元素为'X'或'O'，各尤素间以空格分隔。

输出描述

若有唯一符合要求的最大单入口空闲区域，输出三个数字，第一个数字为入口行坐标(范围为0~行数-1)，第二个数字为入口列坐标(范围为0~列数-1)，第三个数字为区域大小，三个数字以空格分隔:

若有多个符合要求的最大单入口空闲区域，输出一个数字，代表区域的大小;

若没有，输出NUL。

示例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 0 0 0 
X 0 0 0
X 0 0 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

说明：
存在两个大小为3的最大单入口区域，两个入口横纵坐标分别为1,3 和 3,3 

C++

#include <bits/stdc++.h>

using namespace std;

int dfs(int r, int c, vector<vector<char>> &grid, vector<vector<int>> &vis, int group) {
    if (r < 0 || c < 0 || r == vis.size() || c == vis[0].size() || grid[r][c] != 'O' || vis[r][c]) return 0;

    // 给区域标号
    vis[r][c] = group;
    return dfs(r + 1, c, grid, vis, group) +
           dfs(r - 1, c, grid, vis, group) +
           dfs(r, c + 1, grid, vis, group) +
           dfs(r, c - 1, grid, vis, group) + 1;
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<char>> grid(m, vector<char>(n));

    // 读入矩阵数据
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }

    // 维护所有的空闲区域信息<区域号group, <入口行，入口列，区域大小>>
    unordered_map<int, array<int, 3>> entrances;
    vector<vector<int>> vis(m, vector<int>(n));
    for (int i = 0, group = 1; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 位于边界的"0"作为入口
            if (grid[i][j] == 'O' && (i * j == 0 || i + 1 == m || j + 1 == n)) {
                if (vis[i][j]) { // 又发现其他入口,则不是单入口空闲区域则删除掉
                    entrances.erase(vis[i][j]);
                } else {
                    // 递归标记区域并统计区域大小
                    int count = dfs(i, j, grid, vis, group);
                    entrances[group] = {i, j, count};
                    group++;
                }
            }
        }
    }

    // 最大的区域，最大的区域的个数
    int maxCount = 0, cnt = 0;
    array<int, 3> ans{};
    for (auto &p: entrances) {
        if (p.second[2] > maxCount) {
            ans = p.second;
            maxCount = p.second[2];
            cnt = 1;
        } else if (p.second[2] == maxCount) {
            cnt++;
        }
    }

    if (cnt == 0) { // 没有符号要求的结果
        cout << "NULL" << endl;
    } else if (cnt == 1) { // 只有唯一的结果
        cout << ans[0] << " " << ans[1] << " " << ans[2] << endl;
    } else { // 有多个符合要求的单入口空闲区域
        cout << maxCount << endl;
    }

    return 0;
}

代码解析

1. 矩阵输入：首先输入矩阵的大小 m 和 n，然后输入矩阵的每一行。
2. DFS 查找连通区域：dfs 函数递归地探索矩阵中所有连通的 'O'。当发现一个 'O' 时，它会继续探索上下左右四个方向，直到区域完全标记。
3. 入口判断：每次遍历边界上的 'O' 时，我们检查它是否已经访问过，如果访问过，则说明已经处理过这个区域。如果没有访问过，则启动 DFS 进行区域的探索。
4. 区域记录：通过 entrances 字典来记录每个区域的入口坐标和大小。entrances[group] = {i, j, count} 中，group 是区域的标号，i, j 是入口坐标，count 是区域大小。
5. 输出结果：
   • 如果没有符合条件的区域，输出 NULL。
   • 如果有唯一的最大区域，输出该区域的入口坐标和区域大小。
   • 如果有多个最大区域，输出最大区域的大小。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏