242043 - 航拍照片自动裁剪

题目描述

摄影师得到一张 n 行 m 列的黑白航拍照片。# 表示需要保留的目标像素,. 表示背景像素。

为了去掉四周多余背景,需要裁出一个包含全部 # 的矩形。矩形边界必须沿原照片的行、列方向,不能旋转;并且面积要尽可能小。裁剪后矩形内部的背景像素仍要保留。

如果照片至少有一个 #,请输出这个最小矩形在原照片中的边界,以及裁剪后的图案。原照片行号从上到下为 1 到 n,列号从左到右为 1 到 m。

如果没有任何 #,只输出 EMPTY。

输入

输入说明:

第一行两个整数 n,m。

接下来 n 行,每行一个长度为 m 的字符串,只含 # 和 .。

【数据范围】

对全部数据,1\le n,m\le50。

输出

输出要求:

如果没有目标像素,输出一行 EMPTY。

否则,第一行输出四个整数 r_1,c_1,r_2,c_2,依次表示矩形左上角与右下角在原照片中的行、列号,边界均包含。

接下来输出裁剪后的图案,共 r_2-r_1+1 行,每行 c_2-c_1+1 个字符,字符间不加空格。

样例

输入

4 6
......
..##..
.#....
......

输出

2 2 3 4
.##
#..

输入

2 3
...
...

输出

EMPTY
说明

【样例解释1】

所有目标像素位于第2至3行、第2至4列之间,因此保留这两行三列。矩形内部的三个背景像素仍保留。

【样例解释2】

没有目标像素,不输出边界或图案,只输出EMPTY。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 4 枚
难度 基础


上一题 下一题