#21143. 宝藏

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: chf123456

题目描述

柒某人参加了一个密室找宝藏的冒险活动,密室是一个巨大的 n 行 m 列的矩阵。柒某人的视力非常好,她能从密室的一端沿直线看到密室的另一端(但她只能看八个方向——东北,东,东南,南,西南……),而且她跑得非常快,跑一步(向上、下、左、右移动一格)只需要 1s。但密室是不透光的,而且,要破坏密室的墙也不容易,所以柒某人决定绕到一个能够看到宝藏的地方。现在,柒某人希望你能帮她确定最短需要多长时间才能得到宝藏。

输入格式

第一行为 2 个数 N,M 表示密室的规模(N 为高,M 为宽)

接下来是 N×M 的密室,O 表示空地,X 表示墙。

最后是多对数据,分别是宝藏坐标及柒某人的坐标。

输出格式

根据每对数据,计算柒某人拿到宝藏的最短时间,每对一行。如果有意难为柒某人,用墙将宝藏包围了起来,输出 Impossible。

样例

3 4
OXXO
XXOO
XOOO
3 2 2 4
3 3 1 1

1
Impossible

数据范围与提示

1<=n,m<=1000