#3808. Neerc2012 Labyrinth of the Minotaur

题目描述

有一个四连通的h行w列(h,w≤1500)的迷宫，有些

格子里有障碍物。左上角的格子记作(1,1)，右下角的

格子记作(h,w)，这两个格子内都没有障碍物。

求一个最小的不包含(1,1)和(h,w)的正方形区域，使

得这个区域中没有障碍物，并且在区域中填充障碍物

之后，(1,1)和(h,w)就不连通了。

输入格式

输出格式

样例

样例输入

116  

......#####  

.#.#...#..#  

.#.#.......  

.......###.  

#####.###..  

#####......

样例输出

2 6 3

数据范围与提示

无解时输出"Impossible"