#P3808. Neerc2012 Labyrinth of the Minotaur
Neerc2012 Labyrinth of the Minotaur
题目描述
一个迷宫有 行、 列。. 表示空地,# 表示墙。只能在共用一条边的空地格之间移动。入口在左上角 ,牛头怪的巢穴在右下角 。保证这两个格子都是空地,且原本互相可达。
你要选一个边与网格平行的正方形,将其中的格子全部变成墙,使入口与巢穴不再连通。正方形中的所有格子原先必须是空地,并且不能覆盖入口或巢穴。求边长最小的这样的正方形。
输入格式
第一行两个整数 (),分别表示列数和行数。
接下来 行,每行 个字符 . 或 #,从上到下描述迷宫。
输出格式
若有解,输出三个整数 ,分别表示正方形的边长、左上角的列号和行号。列从左向右、行从上到下,均从 开始编号。如果有多个边长最小的方案,输出任意一个。
若无解,输出 Impossible。
样例
11 6
......#####
.#.#...#..#
.#.#.......
.......###.
#####.###..
#####......
2 6 3