UVa12863 - Journey through the kingdom(A*搜尋 、2D BIT)

UVa
字數統計： 3.1k   |   閱讀時間≈ 13分鐘

題目大意

ICPC 是一家保全公司，負責將重要的資料從 A 地搬運到 B 地，此地圖是個表格，我們會告訴你每一個點 (i,j)，能夠到的最大的距離與成本，接下來請寫一個程式告訴我們從 A 地到 B 地的最小成本。

提供 3 個 n*m 的陣列，第一個是成本陣列、第二個是每一個節點最大可以走幾個 Row、第三個則是每一個節點最多可以走 Column。

此題為嚴格輸出比對，需要完全的嚴謹。
題目連結

重點觀念

  • 最短路徑用法 (dijkstra)
  • RangeTree
    • 選擇要用哪個比較好，BIT or Segment Tree? 這裡要使用 BIT
  • 判斷時間複雜度與了解 Range Tree 每一種資料結構的時間複雜度

分析

好題，好題，這題好題，讓我學到了很多知識，也謝謝 morris 大大讓我在學習知識的路上成長了許多。

首先根據題目要求我們可以明顯知道這題一定是使用 Dijkstra，那現在我們接下來就會遇到一些問題

QUESTION A: 如何判斷 dijkstra 的權重呢

由於題目要求成本必須最小，因此我們一定要設定一個 struct，並且寫一個 operator 讓成本最小的優先讓 queue top，假如成本都一樣時，我們就比較曼哈頓距離誰比較接近終點的優先 top。

1
2
3
4
5
bool operator<(const Node &a) const{
    if(v != a.v) //成本
        return a.v < v ;
    return a.h < h ; //曼哈頓距離
}

QUESTION B: 要如何知道當前節點能走到那些節點呢？

由於每個節點都有可以走訪的最大長度 C(column) or R(row)，因此我們只要判斷\(當前節點 \pm 最大長度 \)，並不讓它超出邊界即可。

1
2
3
4
lr = max(1, u.r-R[u.r][u.c]); rr = min(n, u.r+R[u.r][u.c]);
//lr = 左邊界 rr = 右邊界
lc = max(1, u.c-C[u.r][u.c]); rc = min(m, u.c+C[u.r][u.c]);
// lc = 上邊界 rc = 下邊界

QUESTION C: 要如何知道節點有沒有被走訪過呢？

由於這題的邊都是單向邊，然而我們的目標則是要找出所有未走訪的點加入 queue，我們每次要查找有哪些點沒有被走訪時，可以有這幾種方法

  • for 雙重迴圈查找
    由於每次的時間複雜度都是 \(n^2\)，不理想，因此我們不使用
  • 2D Binary Index Tree
    由於 Binary Index Tree 查詢時間複雜度是 \(O(\log{N})\)，單點修改也是\(O(\log{N})\)，在對於會有大量節點進入 queue 中的 dijkstra 中是一個好選擇
  • 2D Segment Tree
    Segment Tree 與 Binary Index Tree 大致相同，Segment Tree 比 Binary Index Tree 用途更廣泛一些，但 Binary Index Tree 實現過程中較為好寫 ，但因為這裡的矩陣長度一致性極高，不會有區間不相同的問題且區間相同都是 1，因此這裡我們使用 Binary Index Tree。

What are the differences between segment trees, interval trees, binary indexed trees and range trees? - stackoverflow

對於 Binary Index Tree or Segment Tree 我還沒寫出詳解，以後如果有寫會補上。

2D Binary Index Tree 建立、修改、查詢方法

建立 init

在 2D Binary Index Tree 中不會像 1D Binary Index Tree 建立方式完全相同，大致上相同，且每個點都需要新增(modify)初始值。

值得注意的是 2D Binary Index Tree，的最大長度在這題我們會設定不可以大於 Row or Column 的最大數量，因為我們可以透過 2D Binary Index Tree 相減的方式來找出當前節點應該要有的值為何

舉例：我們想要查找 4 的值，那就只需要讓 4 這個節點減掉 2 與 3 這兩個節點就可以知道 4 原本的值

1
2
3
4
5
6
7
8
9
10
11
int A[MAXN][MAXN] ;
int R , C ;
void init(int _R, int _C){
    R = _R ;
    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);
    }
}

modify 修改

2D Binary Index Tree，使用雙重迴圈，由於是二維的因此 x,y 座標都必須使用 lowbit 且 y 軸必須因為 x 軸的變化而變回 1。

1
2
3
4
5
6
void modify(int x, int y, int val){
    for(; x <= R ; x += lowbit(x)){
        for(int i = y ; i <= C ; i += lowbit(i))
            A[x][i] += val;
    }
}

query 查詢

這是與 1D Binary Index Tree，最不同的地方，因為 2D Binary Index Tree 如果只對一個區間查詢如 \((x_1,y_1)\) ~ \((x_2,y_2)\)，如果只對 \((x_2,y_2)\) 進行像 1D Binary Index Tree 查詢就會使查找範圍變為 \((1,1)\) ~ \((x_2,y_2)\)，這裡的 index 從 1 開始，透過圖片來示意即是：

2D Fenwick Tree / 2D Binary Indexed Tree

相信讀者已經大概了解我在說甚麼，為了讓我們的查找範圍可以順利查找成功，因此我們要減去\((x_2,y_1)\) ~ \((0,0)\) 與 \((x_1,y_2)\) ~ \((0,0)\) 再加上 \((x_1,y_1)\) 的範圍來補回我們之前多減的區塊。

可能會有些讀者想問，那我能不能夠一口氣查詢 \((x_1,y_1)\) ~ \((x_2,y_2)\) 的範圍呢？答案是不行的，因為我們在修改值的時候會讓 1 的節點值加給 2 號節點，再讓 2 號節點加給 3 號節點(lowbit) 的效果，因此我們沒有辦法一口氣就查詢完畢。

必須先寫一個 sub query 來讓對每塊長方形進行查詢，在進行加減法來達到我們想查詢的範圍

1
2
3
4
5
6
7
8
9
10
11
int query(int x, int y){ //子查詢 sub query
    int cnt=0 ;
    for(; x > 0 ; x -= lowbit(x)){
        for(int i = y ; i>0 ; i -= lowbit(i))
            cnt += A[x][i] ;
    }
    return cnt ;
}
int rectCnt(int lx, int ly, int rx, int ry){
    return query(rx,ry) - query(lx-1,ry) - query(rx, ly-1) + query(lx-1, ly-1);
}

QUESTION D: 嚴格比對怎麼寫比較好呢？

由於是嚴格比對，因此我們輸出要特別小心，要完全一樣，但比較能夠放心的是我們可以用簡單的寫法去實現即可，也就是當我們讀到最後一筆時再輸出 \n，其他都輸出 space 即可。

1
2
3
4
5
6
7
for(int i=1; i<n; i++){
    cout << findPath(r, c, P[i-1][0], P[i-1][1], P[i][0], P[i][1]) ;
    if(i==n-1)
        cout << '\n';
    else
        cout << ' ';
}

QUESTION E: priority_queue 有沒有清空函式呢

答案是沒有，因此手寫一個迴圈不斷 pop 到 queue 被清空即可。

1
while(!q.empty()) q.pop(); //由於 queue 沒有清空，因此寫個清空

參考來源

心得

這題學到蠻多東西的，也讓我把整個程式碼的排版稍微再重新整理一些，最近學到要讓自己的程式碼風格與大家相同才會讓他人在看我的程式碼時不會感到厭煩，會開心一些。

也謝謝我在學習演算法時網路上提供資源的大神們，讓我在學習的路上可以更輕鬆，有資源讓我進行成長，沒有他們我不知道這題我還要學習多久。

題外話：最近發現寫網頁前端不需要訓練太久，薪水也蠻不錯的就讓我覺得學演算法似乎沒什麼太大幫忙QQ，希望未來可以打翻這個認知，不然會讓我很難過啊，嗚嗚。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

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
#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 512
#define lowbit(x) x&(-x)
using namespace std;
int V[MAXN][MAXN], R[MAXN][MAXN], C[MAXN][MAXN], P[MAXN][2] ;
//V 是成本 R 是可擴長的 row , C 是可擴展的 column , P 是要查詢從某地到某地的紀錄
int TX , TY ; // 終點 x 終點 y

struct Node{ //dijkstra 用到的節點
    int r, c, v, h; // r=x , c=y , h 等於漢明距離 , v 是成本
    Node(int _r=0,int _c=0, int _v=0, int _h=0):  //輸入值可以有這種寫法
        r(_r), c(_c), h(_h), v(_v) {}
    bool operator<(const Node &a) const{ //看大衛的筆記 , UVa 10181 
        if(v != a.v)
            return a.v < v ; //最小
        return a.h < h ;
    }
};

priority_queue<Node> q ; // dijkstra
struct BIT{ // 2D binary indexed tree，狀態樹 注意，這裡是二維
    int A[MAXN][MAXN] ; // 走過的點 1 為還沒走過
    int R , C ;
    void init(int _R, int _C){
        R = _R ;
        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 += lowbit(x)){
            for(int i = y ; i <= C ; i += lowbit(i))
                A[x][i] += val;
        }
    }
    int query(int x, int y){ //sub query
        int cnt=0 ;
        for(; x > 0 ; x -= lowbit(x)){
            for(int i = y ; i>0 ; i -= lowbit(i))
                cnt += A[x][i] ;
        }
        return cnt ;
    }
    int rectCnt(int lx, int ly, int rx, int ry){
        return query(rx,ry) - query(lx-1,ry) - query(rx, ly-1) + query(lx-1, ly-1);
    }
    void update(int lx, int ly, int rx, int ry, int val, int tot){
        //lr = 左邊界 rr = 右邊界
        //lc = 上邊界 rc = 下邊界
        // val 成本 tot 當前還有多少節點

        if(tot == -1) //表示還未查詢過，現在進行查詢
            tot = rectCnt(lx,ly,rx,ry); 
        if(tot == 0) return ; //已經沒有節點，表示都有走訪過
        if(lx == rx){ //先透過 x 進行二分查詢，如果一樣在對 y 進行二分查詢
            if(ly == ry){ //已經抵達未走訪的節點
                q.push(Node(lx, ly, val+V[lx][ly], abs(lx-TX)+abs(ly-TY))); //增加節點
                modify(lx, ly, -1);
                return ;
            }
            int cnt = rectCnt(lx, ly, rx, (ly+ry)/2); //查找二分後的節點，cnt 表示左邊
            if(cnt) //如果左邊還有節點表示還沒有走訪
                update(lx, ly, rx, (ly+ry)/2, val, cnt);
            if(cnt < tot)  //表示右半部還有節點還沒有走訪
                update(lx, (ly+ry)/2 + 1, rx, ry, val, tot - cnt);
        }
        else{
            int cnt = rectCnt(lx, ly, (lx+rx)/2, ry);  //查找二分後的節點，cnt 表示左邊
            if(cnt) //如果左邊還有節點表示還沒有走訪
                update(lx, ly, (lx+rx)/2, ry, val, cnt);
            if(cnt < tot) //表示右半部還有節點還沒有走訪
                update((lx+rx)/2 + 1, ly, rx, ry, val, tot - cnt);
        }
    }
}bit;

int findPath(int n, int m, int sx, int sy, int ex, int ey){ //dijkstra 主題核心
    if(sx == ex && sy == ey ) return 0 ; //當前位置就是終點位置
    TX = ex ; TY = ey ; //設定值
    bit.init(n, m); //建立圖
    bit.modify(sx, sy, -1); //將起點可以走訪到的點都設為 -1
    //clear
    while(!q.empty()) q.pop(); //由於 queue 沒有清空，因此寫個清空
    q.push(Node(sx, sy, V[sx][sy], abs(sx-TX)+abs(sy-TY))); //放入初始節點

    Node u;
    int lr, rr, lc, rc;
    //lr = 左邊界 rr = 右邊界
    //lc = 上邊界 rc = 下邊界
    while(!q.empty()){ //如果節點還沒有被走訪完就繼續 dijkstra
        u = q.top(); q.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]);
        //確認當前節點可以到的最大範圍
        bit.update(lr, lc, rr, rc, u.v, -1); //進行更新，將這些裡面的節點都標示為走訪過
    }
    return -1; //如果無法抵達，那就輸出 -1
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    int r, c, n;

    while(cin >> r >> c >> n){
        for(int i=1; i<=r; i++){ //輸入成本陣列
            for(int j=1; j<=c ;j++)
                cin >> V[i][j] ; 
        }
        for(int i=1; i<=r; i++){ //輸入最大 Row陣列
            for(int j=1; j<=c ;j++)
                cin >> R[i][j] ;
        }
        for(int i=1; i<=r; i++){ //輸入最大 Column 陣列
            for(int j=1; j<=c ;j++)
                cin >> C[i][j] ;
        }
        for(int i=0; i<n; i++) //紀錄所有的目的地
            cin >> P[i][0] >> P[i][1];
        for(int i=1; i<n; i++){ 
            cout << findPath(r, c, P[i-1][0], P[i-1][1], P[i][0], P[i][1]) ;
            if(i==n-1) //嚴格比對，因此這樣寫
                cout << '\n';
            else
                cout << ' ';
        }
    }

    return 0;
}

思考流程

透過紙筆與黑板而思考而成的片段，放在網路上供我紀念XD

  • 版權聲明： 本部落格所有文章除有特別聲明外，均採用 Apache License 2.0 許可協議。轉載請註明出處！
  • © 2020-2024 John Doe
  • Powered by Hexo Theme Ayer
  • PV: UV: