AlgoMooc
← 返回题库

P3517. 查找单入口区域

中等通过率 48% · 提交 222 · 通过 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

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。