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
4 3 3 1.23
....
##..
....
1 1
1 3
4 1
4 3
8.66
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. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define MAX_WIDTH 80
#define MAX_BOMB_NUM 1010
#define MAX_DIST 5626
#define SQRT_2 1.4142135623730950488016887242097

typedef char Map[MAX_WIDTH + 1][MAX_WIDTH + 1];
typedef unsigned char Position[MAX_BOMB_NUM][2];
typedef double Distance[MAX_WIDTH + 1][MAX_WIDTH + 1];

void solveE3b_DieHard();
void inputMap(Map map, int rowNum, int colNum);
void inputBombs(Position bombs, int k);
double bfs(Map map, int rowNum, int colNum, unsigned char srcPos[2], unsigned char destPos[2]);
void initDistance(Distance d, int rowNum, int colNum, int value);
void copyPosition(unsigned char dest[2], unsigned char src[2]);
int canGo(Map map, int rowNum, int colNum, unsigned char position[2]);
void printDistance(Distance map, int rowNum, int colNum);

int main() {
    solveE3b_DieHard();
    return 0;
}

void solveE3b_DieHard() {
    int n, m, k;
    double v;
    Map map;
    Position bombs;

    scanf("%d %d %d %lf", &n, &m, &k, &v);
    inputMap(map, m, n);
    inputBombs(bombs, k);

    double totalDist = 0, currDist;
    unsigned char srcPos[2] = {bombs[0][0], bombs[0][1]};
    for (int i = 1; i <= k; ++i) {
        currDist = bfs(map, m, n, srcPos, bombs[i]);
        if (currDist < MAX_DIST) {
            totalDist += currDist;
            copyPosition(srcPos, bombs[i]);
        }
    }
    printf("%.2lf\n", totalDist / v);
}

void inputMap(Map map, int rowNum, int colNum) {
    for (int i = 1; i <= rowNum; ++i) {
        for (int j = 1; j <= colNum;) {
            scanf("%c", &map[i][j]);
            if (map[i][j] != '\n') ++j;
        }
    }
}

void inputBombs(Position bombs, int k) {
    int x, y;
    for (int i = 0; i <= k; ++i) {
        scanf("%d %d", &x, &y);
        bombs[i][0] = y;
        bombs[i][1] = x;
    }
        
}

unsigned char queue[MAX_WIDTH*MAX_WIDTH][2];
Distance distance;
double bfs(Map map, int rowNum, int colNum, unsigned char srcPos[2], unsigned char destPos[2]) {
    initDistance(distance, rowNum, colNum, MAX_DIST);
    
    int front = 0, rear = 0;
    copyPosition(queue[rear++], srcPos);
    distance[srcPos[0]][srcPos[1]] = 0;

    unsigned char currPos[2], nextPos[2];
    int neighbours[][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, 
                            { -1, 1 }, { 1, 1 }, { 1, -1 }, { -1, -1 } };
    double currDist;
    while (front != rear) {
        copyPosition(currPos, queue[front++]);
        for (int i = 0; i < 8; ++i) {
            nextPos[0] = currPos[0] + neighbours[i][0];
            nextPos[1] = currPos[1] + neighbours[i][1];
            if (canGo(map, rowNum, colNum, nextPos)) {
                if (i < 4) 
                    currDist = distance[currPos[0]][currPos[1]] + 1;
                else
                    currDist = distance[currPos[0]][currPos[1]] + SQRT_2;
                if (currDist < distance[nextPos[0]][nextPos[1]]) {
                    distance[nextPos[0]][nextPos[1]] = currDist;
                    copyPosition(queue[rear++], nextPos);
                }
            }
        }
    }
    // printDistance(distance, rowNum, colNum);
    return distance[destPos[0]][destPos[1]];
}

void copyPosition(unsigned char dest[2], unsigned char src[2]) {
    dest[0] = src[0];
    dest[1] = src[1];
}

void initDistance(Distance d, int rowNum, int colNum, int value) {
    for (int i = 1; i <= rowNum; ++i) {
        for (int j = 1; j <= colNum; ++j) {
            d[i][j] = value;
        }
    }
}

int canGo(Map map, int rowNum, int colNum, unsigned char position[2]) {
    return (position[0] >= 1 && position[0] <= rowNum 
            && position[1] >= 1 && position[1] <= colNum 
            && map[position[0]][position[1]] != '#');
}

void printDistance(Distance map, int rowNum, int colNum) {
    printf("\n");
    for (int i = 1; i <= rowNum; ++i) {
        for (int j = 1; j <= colNum; ++j)
            if (map[i][j] < MAX_DIST)
                printf("%04.2f ", map[i][j]);
            else
                printf("#### ");
        printf("\n");
    }
}