AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

P3517. 查找单入口区域

中等通过率 49% · 提交 218 · 通过 106
DFSBFS矩阵模拟DFS/BFS

小慕正在设计一个 m x n 的网格布局图,图中每个格子要么被标记为 '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

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

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解
单入口空闲区域示例 (4x4 矩阵) X X X X X O O X X O O X X O X X 入口 (3,1) 连通区域大小 = 5 (边界唯一入口)
写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「查找单入口区域」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。