#P3808. Neerc2012 Labyrinth of the Minotaur

    ID: 3010 传统题 1000ms 128MiB 尝试: 61 已通过: 11 难度: 8 上传者: 标签>CF2500提高+/省选-平面图对偶多源 BFS二维前缀和网格 DP二分答案最优性剪枝

Neerc2012 Labyrinth of the Minotaur

题目描述

一个迷宫有 hh 行、ww 列。. 表示空地,# 表示墙。只能在共用一条边的空地格之间移动。入口在左上角 (1,1)(1,1),牛头怪的巢穴在右下角 (h,w)(h,w)。保证这两个格子都是空地,且原本互相可达。

你要选一个边与网格平行的正方形,将其中的格子全部变成墙,使入口与巢穴不再连通。正方形中的所有格子原先必须是空地,并且不能覆盖入口或巢穴。求边长最小的这样的正方形。

输入格式

第一行两个整数 w,hw,h(2≤w,h≤15002\le w,h\le1500),分别表示列数和行数。

接下来 hh 行,每行 ww 个字符 . 或 #,从上到下描述迷宫。

输出格式

若有解,输出三个整数 s,c,rs,c,r,分别表示正方形的边长、左上角的列号和行号。列从左向右、行从上到下,均从 11 开始编号。如果有多个边长最小的方案,输出任意一个。

若无解,输出 Impossible。

样例

11 6
......#####
.#.#...#..#
.#.#.......
.......###.
#####.###..
#####......
2 6 3

NEERC 2012 组委会原题,Problem L