米诺陶洛斯的迷宫 Labyrinth of the Minotaur

牛头怪是生活在克里特岛迷宫中的半公牛半人生物。他恐吓整个克里特岛，特别是米诺斯城。每年都有七个小男孩和小女孩被送到迷宫去取悦牛头怪。每次献祭之后，牛头怪都会睡一会儿。 忒修斯，这位半神半人的希腊英雄，刚刚来到弥诺斯。米诺斯人要求他杀死米诺陶尔人。不幸的是，牛头怪不是一个容易杀死的目标。忒修斯甚至怀疑他杀死熟睡中的牛头怪的能力。于是他决定把牛头怪关在自己的迷宫里。 迷宫有一个矩形，被分成大小相等的正方形格子。每个单元格要么为空，要么为阻塞。即使是人身牛头怪也无法通过被阻断的单元格。迷宫的入口位于迷宫的一个角落，而牛头怪的巢穴位于相反的角落。 忒修斯只有一次机会阻止牛头怪。构建障碍的单元格必须是空的。如果从牛头怪的巢穴到迷宫的入口没有路，它就会被封锁。 当然，障碍不能阻挡牛头怪的巢穴(你不能在牛头怪的巢穴上建造任何东西，即使是在睡觉的地方)，也不能阻挡入口的巢穴(忒修斯不能完全阻挡迷宫)。 你必须计算出能够阻挡牛头怪的方形障碍物的最小的可能的大小。 输入 输入将包含几个测试用例，每个测试用例如下所述。输入的第一行包含一对正整数w和h迷宫的宽度和高度 (2 ≤ w, h ≤ 1500)。下面的h线包含迷宫的地图。每个字符的长度都是w。空单元格用点('.')表示。通过数字符号('#')阻断细胞。入口位于左上角(单元格(1,1))，牛头怪巢穴位于右下角(单元格(w, h))。这两个单元格都是空的，而且从牛头怪巢穴的入口至少有一条路。 输出 对于每个测试样例，单独写入一行输出。 输出3个整数l, x和y，能够阻挡迷宫内牛头怪的最小方形障碍物的边长，以及其左上角单元格的坐标。如果存在多对可能的坐标，则输出任意一对。障碍不能包含任何被阻塞的单元格，以及迷宫入口或牛头怪巢穴。如果不可能建造一个方形障碍物来阻挡牛头怪，输出一个 “Impossible”。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4567 [PDF](https://uva.onlinejudge.org/external/16/p1692.pdf)