# 1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1643

## 1643. Attack of the Dark Fortress

Time limit: 1.0 second
Memory limit: 64 MB
Knowing that lich Sandro left to fight the King of Hell, Erathian commanders decided to take advantage of his absence and take over the Dark Fortress. An army of crusaders led by Catherine Ironfist set out from Steadwick. On the same day an army of elven snipers led by Gelu set out from the forests of AvLee. The commanders realize that infantry is vulnerable to liches, and the elven arrows are ineffective against the skeletons, hence the two armies should unite and attack the Fortress simultaneously. As Sandro may return any moment, the Fortress should be attacked as soon as possible. As a court cartographer, you are to calculate the number of days required to implement this plan.
Erathia is divided into square regions. Some of them are passable, some of them are not. On one day, each army can move to one of the adjacent (sharing a vertex with a current region) passable regions. Some of the Erathian passable regions have a teleport of one of 26 types inside. A type of a teleport is indicated by a capital Latin letter. If an army is located in a region with a teleport, it can move to any region with a teleport of the same type instantly. When two armies are located in the same region, they unite and then start to move as a single army. No army can attack the Fortress (that is, make a move to the region the Fortress is located in) before the union.

### Input

The first line contains space-separated integers n and m — dimensions of the map of Erathia (1 ≤ n, m ≤ 100). Then the map itself follows — n lines of m characters each. The meaning of the characters:
‘#’ indicates impassable region.
‘.’ indicates passable region.
‘A’…’Z’ indicates a teleport of type corresponding to that letter.
‘$’ indicates Catherine’s army. ‘!’ indicates Gelu’s army. ‘*’ indicates the Fortress. It is guaranteed that the characters ‘*’, ‘$’, ‘!’ are encountered exactly once on the whole map.

### Output

Output a single integer — the number of days that should pass before the united army can attack the Fortress. If the Fortress can’t be attacked, output “Impossible”.

### Samples

input output
Problem Author: Denis Dublennykh
Problem Source: USU Junior Contest, October 2008

## 2. 思路

BFS完成后，遍历与终点相邻的8个位置，对于位置(i, j)，如果 distCath[i][j] 和 distGelu[i][j] 都有合法值，说明铠煞麟和嗝噜两人可以在此处会师，max( distCath[i][j] , distGelu[i][j] )即为一个候选结果，找出最小的候选结果即可。如果一个候选结果都没有，则判定失败。