#3808. Neerc2012 Labyrinth of the Minotaur

内存限制:128 MiB 时间限制:40 Sec

题目描述

有一个四连通的h行w列(h,w≤1500)的迷宫,有些
格子里有障碍物。左上角的格子记作(1,1),右下角的
格子记作(h,w),这两个格子内都没有障碍物。
求一个最小的不包含(1,1)和(h,w)的正方形区域,使
得这个区域中没有障碍物,并且在区域中填充障碍物
之后,(1,1)和(h,w)就不连通了。

输入格式

输出格式

样例

样例输入


			
116
......#####
.#.#...#..#
.#.#.......
.......###.
#####.###..
#####......

样例输出


			
2 6 3

数据范围与提示

无解时输出“Impossible“