解題區/解題區 - UVa

UVa 12863 - Journey through the kingdom

contents

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

Problem

對於每一個點 (i, j) 可以護送人的範圍為中間張開矩形 [i-r: i+r] x [j - c: j+c]，可以傳送到矩形任何一點花費為 V(i, j)。每個點的花費和矩形大小都可以不同。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3 4 5
1 2 1 1
1 5 3 4
1 1 6 3
1 2 3 3
3 3 1 2
0 0 0 1
1 4 0 1
2 3 0 1
4 1 3 1
1 1
3 4
1 1
2 2
2 2

Sample Output

1
3 -1 1 0

Solution

什麼，居然有 range tree 配上 dijkstra？

很明顯是一題最短路徑。所有點都分配在 N x M 上，最慘為 25 萬個點，同時邊最慘邊數量也就是 25 萬 x 25 萬，因此在 O(E log V) 肯定是過不去的。

但是後來發現到，花費是在點上，因此可以換個角度想，每次更新離開該點花費最小的，也就是說每 pop 一個點，就能知道有一個矩形內保證是最短路，不會再進行任何更新。因此只要不斷地找到區域內尚未走訪的點，將其移除即可。

為了能夠快速找到矩形內尚未走訪的點，最好的方式是使用 range tree，但是找到區域內所有點的成本是 O(log^2 n + k)，用一堆 set<int> 串 list 起來也要 O(r log n + k)，這種作法會 TLE。而標程中使用 BIT 完成 range tree 的概念，BIT 查找速度是挺快的，但是看起來比較接近 O(k log^2 n)，只能說點移除的速度很快，所以 k 小很多。

用 2D BIT 作為 range tree 的基底，也要確保每一個點很緊密地在 R x C 的每一格，range tree 找到區域內所有尚未走訪的點，進行 dijkstra 更新。

自己寫一個樹套樹的作法嘗試輾輾看，但是在建表上就已經快崩，記憶體飛漲得相當快，導致速度被拉下。之後改用一個 list 串出一堆一條一條的 set，這樣的速度，隨後用二分處理，比用 2D BIT 建造的 range tree 還要快，至少在隨機測資中速度是兩三倍以上，上傳 TLE。

看來只能乖乖地標程給的 … WTF，居然就這樣屈服了，都寫了好幾個版本。就不能讓我混過嗎。QAQ

當前使用優化策略： 建立於 dijkstra

  • 方案 1：
    (1) 啟發式搜索，相同花費下鄰近目標地的優先擴充，沒有好的估價。
    (2) 對於矩形，每個 row 當作一條，建立 list，把不可能需要更新的點移除，實作由 set row[MAXN] 完成。
  • 方案 2：
    (1) 啟發式搜索，相同花費下鄰近目標地的優先擴充，沒有好的估價。
    (2) 對於矩形，random 矩形內部 K 個點。
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <set>
#include <algorithm> 
using namespace std;
#define MAXN 512
int V[MAXN][MAXN], R[MAXN][MAXN], C[MAXN][MAXN];
int TX, TY;
struct Node {
    int r, c, v, h;
    Node(int a=0, int b=0, int d=0, int e=0):
    r(a), c(b), v(d), h(e) {}
    bool operator<(const Node &x) const {
        if (v != x.v)
            return v > x.v;
        return h > x.h;
    }
};
priority_queue<Node> pQ; // dijkstra
struct RangeTree { // 2D binary indexed tree
    int A[MAXN][MAXN];
    int R, C;
    void init(int R, int C) {
        this->R = R, this->C = C;
        memset(A, 0, sizeof(A));
        for (int i = 1; i <= R; i++)
            for (int j = 1; j <= C; j++)
                modify(i, j, 1);
    }
    
    void modify(int x, int y, int val) {
        for (; x <= R; x += x&(-x)) {
            for (int i = y; i <= C; i += i&(-i)) 
                A[x][i] += val;
        }
    }
    int query(int x, int y) {
        int ret = 0;
        for (; x > 0; x -= x&-x)
            for (int i = y; i > 0; i -= i&(-i))
                ret += A[x][i];
        return ret;
    }
    int rectSum(int lx, int rx, int ly, int ry) {
        return query(rx, ry) - query(lx-1, ry) - query(rx, ly-1) + query(lx-1, ly-1);
    }
    void update(int lx, int rx, int ly, int ry, int val, int tot) { // {val: update cost, tot: #unvisited point in area.}
        if (tot == -1) 	
            tot = rectSum(lx, rx, ly, ry);
        if (tot == 0) 	return;
        if (lx == rx) {
            if (ly == ry) {
                pQ.push(Node(lx, ly, val + V[lx][ly], abs(lx-TX) + abs(ly-TY)));
                modify(lx, ly, -1);
                return;
            }
            int cnt = rectSum(lx, rx, ly, (ly + ry)/2);
            if (cnt) 
                update(lx, rx, ly, (ly + ry)/2, val, cnt);
            if (cnt < tot) 
                update(lx, rx, (ly + ry)/2 + 1, ry, val, tot - cnt);
        }
        else {
            int cnt = rectSum(lx, (lx + rx)/2, ly, ry);
            if (cnt) 
                update(lx, (lx + rx)/2, ly, ry, val, cnt);
            if (cnt < tot)
                update((lx + rx)/2 + 1, rx, ly, ry, val, tot - cnt);
        }
    }
} rangeTree;
int findPath(int n, int m, int sx, int sy, int ex, int ey) {
    if (sx == ex && sy == ey)	return 0;
    TX = ex, TY = ey;
    rangeTree.init(n, m);
    rangeTree.modify(sx, sy, -1);
        
    while (!pQ.empty())	pQ.pop();
    pQ.push(Node(sx, sy, V[sx][sy], abs(sx-ex) + abs(sy-ey)));
    
    Node u;
    int lr, rr, lc, rc;
    while (!pQ.empty()) {
        u = pQ.top(), pQ.pop();
        
        if (abs(u.r - ex) <= R[u.r][u.c] && abs(u.c - ey) <= C[u.r][u.c])
            return u.v;
            
        lr = max(1, u.r - R[u.r][u.c]), rr = min(n, u.r + R[u.r][u.c]);
        lc = max(1, u.c - C[u.r][u.c]), rc = min(m, u.c + C[u.r][u.c]);
        rangeTree.update(lr, rr, lc, rc, u.v, -1);
    }
    return -1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    int n, m, q, X[16], Y[16];
    while (scanf("%d %d %d", &n, &m, &q) == 3) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &V[i][j]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &R[i][j]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &C[i][j]);
        for (int i = 0; i < q; i++)
            scanf("%d %d", &X[i], &Y[i]);
            
        for (int i = 1; i < q; i++) {
            int r = findPath(n, m, X[i-1], Y[i-1], X[i], Y[i]);
            printf("%d%c", r, i == q - 1 ? '\n' : ' ');
        }
    }
    return 0;
}
/*
 3 4 5
 1 2 1 1
 1 5 3 4
 1 1 6 3
 1 2 3 3
 3 3 1 2
 0 0 0 1
 1 4 0 1
 2 3 0 1
 4 1 3 1
 1 1
 3 4
 1 1
 2 2
 2 2
 */