logo AlgoBeat OnlineJudge
登录 注册

#103808. [BZOJ 3808] Neerc2012 Labyrinth of the Minotaur

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定一个四连通的 的迷宫,有障碍物的格子记为 #,没有障碍物的格子记为 .

求一个内部不包含障碍物的正方形,使其满足将它填满障碍物后 不连通或报告不存在解。

输入格式

第一行两个整数

接下来 行,每行 个字符描述这个迷宫。

输出格式

若存在这样的正方形,输出三个整数 表示一个以 作为左上角,边长为 的正方形作为答案;否则输出一行一个 Impossible

样例

样例输入 #1

11 6
......#####
.#.#...#..#
.#.#.......
.......###.
#####.###..
#####......

样例输出 #1

2 6 3

数据范围与提示

对于 的数据,