URAL 1254. Die Hard

1. 题目

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

1254. Die Hard

Time limit: 5.0 second
Memory limit: 64 MB

Problem illustration

There is a city with a grid of square blocks of the N × M size. There are buildings in some blocks, some blocks are blank. John is in the block (x0, y0). He may move from a block to an adjacent one in horizontal, vertical or diagonal direction with velocity V. He is told over the radio the list of points where bombs are located. John is to disarm them in the same order that they follow in the list or he will die hard with a vengeance. If he can’t reach some bomb he moves to the next one. All the bombs are located outside the buildings.
What minimal time will John need to finish his job if he disarms a bomb immediately?

Input

The first line contains numbers N, M, K (an amount of bombs) and V, separated with a space, satisfying the restrictions 1 ≤ N, M ≤ 75; 1 ≤ K ≤ 1000; 0.01 < V < 10.00. Then a city map follows: M lines of N symbols. The symbol ‘.’ means a blank block, ‘#’ stands for a building. Then follow the line that contains coordinates (x0, y0). The input is ended by K lines with bombs coordinates in that very order that John passed them.

Output

You should output the single number which is the minimal time necessary to do the job. The time should be printed with two digits after a decimal point.

Sample

input output
Problem Author: Pavel Atnashev
Problem Source: Open collegiate programming contest for student teams, Ural State University, March 15, 2003

2. 思路

给出带有障碍物的地图,和若干炸弹的位置,要求按顺序解除炸弹;如果炸弹不可达,则跳过并继续尝试下一个。移动速度固定为1格/秒,求解除所有炸弹所需最短时间。 

从起点(x0, y0)开始,BFS搜索第1个炸弹:如果找到,则记下移动距离,以第1个炸弹为起点,BFS搜索第下一个炸弹;如果找不到,则起点不变,BFS搜索下一个炸弹。以此类推,直到搜索完所有的炸弹,根据所得总移动距离得到所需时间。

3. 代码