问题 1924. -- 龙&虫

1924: 龙&虫

时间限制: 1 Sec  内存限制: 128 MB
提交: 82  解决: 12
[提交][状态][讨论版]

题目描述

给出一张N*M的地图,在地图上有一只虫,样子却很像龙,而且嘴能快速的喷出一种毒游,瞬间杀死敌人。
现在假设虫的初始位置在(X1,Y1),另外在(X2,Y2)处有一个敌人。虫能向上、下、左、右四个方向移动,假设虫移动一步需要单位1的时间,而杀死敌人不需要时间,并且虫的毒液射程无穷大,但毒液不能穿透阻碍物,虫只能攻击上、下、左、右、左上、左下、右上、右下八个方向。
请求出虫最少需要用多少时间才能消灭敌人。

输入

第1行为2个数N和M,表示矩阵的规模。(N为高,M为宽,均不超过128)。
接下来N*M的矩阵,O表示空地,X表示障碍物。
下面是若干行数据,每行为一对数据,分别是敌人的位置和虫的位置。显然,敌人和虫都不可能在障碍物上。
以“0 0 0 0”为输入结束标志。

输出

输出若干行,每行一个数据为虫能消灭敌人的最短时间。
显然,若能直接打到敌人,则时间为0;若无法消灭,则输出"Impossible!"。

样例输入

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

样例输出

1
Impossible!

提示

来源

[提交][状态]