小慕正在设计一个 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