URAL 1254. Die Hard

1. 题目


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?


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.


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.


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

2. 思路


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

3. 代码