Coronavirus
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

众所周知,新型冠状病毒的传染性比较强。有一天多多想出家门买东西,但是从家到超市可能会经过高危地段,他想远远的避开这些高危地段并且走最少的路到达超市。
多多每次可以向上、下、左、右四个方向移动。如果一个地段高危,那么多多不会通过高危地段自身及其八个方向的地段。(高危地段自身以及上、下、左、右、左上、左下、右上、右下的地段都不能通过)
如果超市位于高危地段的八个方向内,那么多多不能到达超市。请问他能顺利到达超市吗?如果能的话输出最短路径长度,否则输出"Impossible"。

输入描述:

输入第一行包含两个正整数N,M (1 ≤ N ≤ 50,1 ≤ M ≤ 50)
接下来N行输入长度为M的字符串
字符'S'为家的位置,'E'为超市的位置,'.'代表可走地段,'*'代表高危地段

输出描述:

输出一个整数(最短路径长度)或字符串"Impossible"
示例1

输入

复制
3 3
*..
...
.SE

输出

复制
1
示例2

输入

复制
3 3
S..
...
*.E

输出

复制
4
示例3

输入

复制
3 3
S..
...
.*E

输出

复制
Impossible