URAL 1643. Attack of the Dark Fortress

1. 题目


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.


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 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”.


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

2. 思路


花式BFS。先从铠煞麟的起点开始进行BFS,障碍物是传统项目了,传送门的设定比较新颖,BFS到一个传送门X后,同时把所有传送门X的位置入队即可。由于还有两支队伍需要汇合的要求,BFS不能在搜到终点时立即停止,而是需要访问到所有可以访问的位置(即队列为空)。先从铠煞麟的起点开始BFS,用一个矩阵 distCath[i][j] 记录铠煞麟到达位置(i, j)所需的步数;再从嗝噜的起点开始进行BFS,用一个矩阵 distGelu[i][j] 记录嗝噜到达位置(i, j)所需的步数。

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