解題區/解題區 - UVa

UVa 938 - Gilix

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一個環狀的蜂巢式地圖，上下沒有包裹，只有左右是相連的。現在在某一個蜂巢中放置特殊藥水，走到那個放置處喝下，之後所需要的花費都會砍半。求某點到某點的最少花費。

Sample Input

1
2
3
4
5
6
7
8
4 8
4 2 2 2 4 4 6 10
2 6 8 4 4 4 4 2
8 2 6 8 4 4 4 6
6 4 4 6 8 4 4 4
0 0
3 4
1 1

Sample Output

1
18

Solution

類似最短路徑，不過狀態為 dist[N][2] 是否已經經過放置藥水的地點，隨著 spfa 更新即可。關於蜂巢地圖，直接根據奇偶數 row 分開討論即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int g[512][512];
int dist[512][512][2], inq[512][512][2];
const int dx1[] = {-1, -1, 0, 1, 1, 0};
const int dy1[] = {0, 1, 1, 1, 0, -1};
const int dx2[] = {-1, -1, 0, 1, 1, 0};
const int dy2[] = {-1, 0, 1, 0, -1, -1};
void spfa(int L, int C, int sx, int sy, int ex, int ey, int px, int py) {
    memset(dist, 63, sizeof(dist));
    queue<int> X, Y, S;
    int tx, ty, ts, ss;
    dist[sx][sy][0] = 0;
    X.push(sx), Y.push(sy), S.push(0);
    while (!X.empty()) {
        sx = X.front(), X.pop();
        sy = Y.front(), Y.pop();
        ss = S.front(), S.pop();
        inq[sx][sy][ss] = 0;
        for (int i = 0; i < 6; i++) {
            if (sx&1)
                tx = sx + dx1[i], ty = sy + dy1[i];
            else
                tx = sx + dx2[i], ty = sy + dy2[i];
            if (tx < 0 || tx >= L)	continue;
            ty = (ty + C)%C;
            ts = ss;
            int cost = ts ? g[tx][ty]/2 : g[tx][ty];
            if (tx == px && ty == py)
                ts = ss | 1;
            if (dist[tx][ty][ts] > dist[sx][sy][ss] + cost) {
                dist[tx][ty][ts] = dist[sx][sy][ss] + cost;
                if (!inq[tx][ty][ts]) {
                    inq[tx][ty][ts] = 1;
                    X.push(tx), Y.push(ty), S.push(ts);
                }
            }
        }
    }
    printf("%d\n", min(dist[ex][ey][0], dist[ex][ey][1]));
}
int main() {
    int L, C;
    int sx, sy, ex, ey, px, py;
    while (scanf("%d %d", &L, &C) == 2) {
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < C; j++)
                scanf("%d", &g[i][j]);
        }
        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        scanf("%d %d", &px, &py);
        spfa(L, C, sx, sy, ex, ey, px, py);
    }
    return 0;
}
/*
4 8
4 2 2 2 4 4 6 10
2 6 8 4 4 4 4 2
8 2 6 8 4 4 4 6
6 4 4 6 8 4 4 4
0 0
3 4
1 1
*/