2011-12-08 21:15:14| 人氣1,673| 回應0 | 上一篇 | 下一篇

[UVA] 10653 - Bombs! NO they are Mines!!

推薦 0 收藏 0 轉貼0 訂閱站台

Problem C

Bombs! NO they are Mines!!

Input: standard input
Output: standard output

Time Limit: 4 seconds

It's the year 3002. The robots of "ROBOTS 'R US (R:US)" have taken control over the world. You are one of the few people who remain alive only to act as their guinea pigs. From time to time the robots use you to find if they have been able to become more intelligent. You, being the smart guy, have always been successful in proving to be more intelligent.

Today is your big day. If you can beat the fastest robot in the IRQ2003 land, you'd be free. These robots are intelligent. However, they have not been able to overcome a major deficiency in their physical design -- they can only move in 4 directions: Forward, Backward, Upward and Downward. And they take 1 unit time to travel 1 unit distance. As you have got only one chance, you're planning it thoroughly. The robots have left one of the fastest robot to guard you. You'd need to program another robot which would carry you through the rugged terrain. A crucial part of your plan requires you to find the how much time the guard robot would need to reach your destination. If you can beat him, you're through.

Bomb! No they are mines

Sample input scenario

S- source, D- Destination

We must warn you that the IRQ2003 land is not a pleasant place to roam. The R:US have dropped numerous bombs while they invaded the human land. Most of the bombs have exploded. Still some of the bombs remain acting as land mines. We have managed to get a map that shows the unsafe regions of the IRQ2003 land; unfortunately your guard has a copy of the map, too. We know that at most 40% of the area can be unsafe. If you are to beat your guard, you'd have to find his fastest route long before he finds it.

Input

Input consists of several test cases. Each test begins with two integers R (1 <= R <= 1000), C (1 <= C <= 1000) -- they give you the total number of rows and columns in the grid map of the land. Then follows the grid locations of the bombs. It starts with the number of rows, (0 <= rows <= R) containing bombs. For each of the rows, you'd have one line of input. These lines start with the row number, followed by the number of bombs in that row. Then you'd have the column locations of that many bombs in that row. The test case ends with the starting location (row, column) followed by your destination (row, column). All the points in the region is in the range (0,0) to (R-1, C-1). Input ends with a test case where R=0 and C=0, you must not process this test case.

Output

For each test case, print the time the guard robot would take to go from the starting location to the destination.

Sample Input Output for Sample Input

10 10

0 1 2

1 1 2

2 2 2 9

3 2 1 7

5 3 3 6 9

6 4 0 1 2 7

7 3 0 3 8

8 2 7 9

9 3 2 3 4

0 0

9 9

0 0

作法 : A* Algorithm 擴展
比 BFS 快很多, 但是需要多一些記憶體

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxL 1000
int map[maxL][maxL], L, dx2, dy2;
int sx, sy, ex, ey, R, C;
struct Heap {
   long long F;
   short x, y;
} Heap[maxL*maxL], T;
void Swap(int P, int S) {
   static struct Heap T;
   T = Heap[P], Heap[P] = Heap[S], Heap[S]= T;
}
void siftUp(int set) {
   static int S, P;
   S = set, P = set>>1;
   while(S >= 2 && Heap[P].F > Heap[S].F)
       Swap(P, S), S = P, P = S>>1;
}
void siftDown(int set) {
   static int S, P;
   S = set<<1, P = set;
   while(S <= L) {
       if(S < L && Heap[S+1].F < Heap[S].F)
           S++;
       if(Heap[P].F <= Heap[S].F)
           break;
       Swap(P, S), P = S, S = P<<1;
   }
}
void insVal(int set, long long F, int x, int y) {
   Heap[set].F = F;
   Heap[set].x = x, Heap[set].y = y;
   siftUp(set);
}
void delMin() {
   Swap(1, L), L--;
   siftDown(1);
}
long long H(int cx, int cy) {
   static int dx1, dy1;
   dx1 = cx-ex, dy1 = cy-ey;
   return ((abs(cx-ex)+abs(cy-ey))<<20) + abs(dx1*dy2-dx2*dy1);
}
void Expand(int nx, int ny, int cx, int cy) {
   if(nx < 0 || ny < 0 || nx >= R || ny >= C)
       return;

    if(map[nx][ny] != -1 && map[nx][ny] == 0) {
        map[nx][ny] = map[cx][cy]+1;
        L++, insVal(L, (map[nx][ny]<<20)+H(nx, ny), nx, ny);
    }
}
void AStar() {
    int i, cx, cy;
    L = 1, insVal(L, 0, sx, sy);
    dx2 = sx-ex, dy2 = sy-ey;
    while(L > 0) {
        cx = Heap[1].x, cy = Heap[1].y;
        if(cx == ex && cy == ey)    break;
        delMin();
        Expand(cx+1, cy, cx, cy);
        Expand(cx-1, cy, cx, cy);
        Expand(cx, cy+1, cx, cy);
        Expand(cx, cy-1, cx, cy);
    }
    printf("%d\n", map[ex][ey]);
}
int main() {
    int n, t, row, x;
    int i, j;
    while(scanf("%d %d", &R, &C) == 2) {
        if(R == 0 && C == 0)    break;
        scanf("%d", &n);
        memset(map, 0, sizeof(map));
        for(i = 0; i < n; i++) {
            scanf("%d %d", &row, &t);
            while(t--) {
                scanf("%d", &x);
                map[row][x] = -1;
            }
        }

        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        AStar();
    }
    return 0;
}

我要檢舉

#10653#Bombs!#NO they are Mines!!

台長： Morris

您可能對以下文章有興趣

[UVA][bfs] 10477 - The Hybrid Knight

[UVA][Trie][大數] 12333 - Revenge of Fibonacci

[UVA][匈牙利匹配] 670 - The dog task

[UVA] 858 - Berry Picking

人氣(1,673) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 12347 - Binary Search Tree
此分類上一篇:[UVA] 484 - The Department of Redundancy Department

回應(0)