UVa10259 - Hippity Hopscotch(SPFA、dijkstra、Directed Acyclic Graph)

題目大意

小時候大家都有玩過跳格子八XD，現在我們對跳格子再增加一些規則，格子中都有錢，每個人從 (1,1) 出發，可以水平或垂直跳至多 K 格，但跳到下一個格子時，下一個格子的錢必須比現在的格子還要多
請問最多可以拿多少錢

題目連結

重點觀念

• 演算法知識 - Directed Acyclic Graphby 大衛的筆記

分析

• 由於我們可以理解出這題是 DAG，無向圖，不會有 circle(每次跳得格子都必須比現在的格子大)，因此用 SPFA 來解。
• 只要根據上下左右並且對可抵達的格子進行查詢，看是否能夠擴展即可。

參考連結

[UVa] 10259 - Hippity Hopscotch by Hi, I am Code

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 110
#define INF 0x3f3f3f
using namespace std;
int g[MAXN][MAXN]; //題目
int ans[MAXN][MAXN]; //當前格子可收集到的最大數量
int t, n, k, collect = 0;

int bfs(){
    memset(ans, 0, sizeof(ans));
    deque<pair<int,int> > q;
    q.push_back({1,1});
    ans[1][1] = g[1][1];
    collect = g[1][1];

    while(!q.empty()){
        pair<int,int> node = q.front(); q.pop_front();
        int x = node.first, y = node.second;
        //cout << x << " " << y << " " << collect << "\n";
        //cout << (x+9 <= n && g[x+9][y] > g[x][y] && ans[x][y] + g[x+9][y] > ans[x+9][y]) << " " << g[x+9][y] << "\n";

        for(int i = 1; i <= k; i++){ //對可抵達距離(1~K) 展開擴展
            //cout << "i= " << i << " " << g[x+k][y]<< "\n";

            //擴展時必須比原先的 ans 還要大，這樣才有擴展的理由
            if(x+i <= n && g[x+i][y] > g[x][y] && ans[x][y] + g[x+i][y] > ans[x+i][y]){ //左
                 ans[x+i][y] = ans[x][y] + g[x+i][y];
                 collect = max(ans[x+i][y], collect);
                 q.push_back({x+i,y});
            }
            if(x-i > 0 && g[x-i][y] > g[x][y] && ans[x][y] + g[x-i][y] > ans[x-i][y]){ //右
                 ans[x-i][y] = ans[x][y] + g[x-i][y];
                 collect = max(ans[x-i][y], collect);
                 q.push_back({x-i,y});

            }
            if(y + i <= n && g[x][y+i] > g[x][y] && ans[x][y] + g[x][y+i] > ans[x][y+i]){ //下
                 ans[x][y+i] = ans[x][y] + g[x][y+i];
                 collect = max(ans[x][y+i], collect);
                 q.push_back({x,y+i});
            }
            if(y - i > 0 && g[x][y-i] > g[x][y] && ans[x][y] + g[x][y-i] > ans[x][y-i]){ //上
                 ans[x][y-i] = ans[x][y] + g[x][y-i];
                 collect = max(ans[x][y-i], collect);
                 q.push_back({x,y-i});
            }

        }
    }
    return collect;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> k;
        memset(g, -1, sizeof(g)); //輸入資料
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                cin >> g[i][j];
            }
        }
        cout << bfs() << "\n";
        if(t) cout << "\n"; //最後只需要一個斷行 

//        for(int i = 1; i <= n; i++){
//            for(int j = 1; j <= n; j++){
//                cout << ans[i][j] << " ";
//            }
//            cout << "\n";
//        }
    }
    return 0;
}