UVa10913 - Walking on a Grid(DP、DFS)

題目大意

有一個 \(n*n\) 的棋盤，你從 (1,1) 出發抵達到 (n,n)，其中棋盤裡面的格子都有不同的權重(有正負數)，請告訴我從 (1,1) 抵達 (n,n) 最大路徑是多少，有一些規則你必須遵守

• 每一個格子只能走一次
• 只能夠往下、往左、往右行走
• 給你 k 號數字表示，你最多能夠經過 k 個負數格

重點觀念

演算法知識 - Directed Acyclic Graph by 大衛的筆記

分析

• 理論上使用 SPFA 來進行搜尋，但是可以向左走、對於行走負數限制，讓 SPFA 相對沒那麼好解
• 因此我們將 SPFA 進行拆解，原先我們是使用 BFS，但是因為每一個格子只能夠使用用一次，使用 BFS 就無法將路徑延續性儲存下來(不好儲存)，這時候則使用與 BFS 等價的 DFS
• 搭配 DP 使用，如果 DFS 的節點比當前 DP 大就繼續 DFS，否則就不需要

參考連結

uva 10913 - Walking on a Grid（记忆化）by CSDN

心得

最近太久沒有寫演算法，腦袋有點笨阿QQ

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define INF 10000000
#define int long long
using namespace std;
const int N = 80;
int dp[N][N][10][5], visit[N][N]; //dp[x][y][走了幾個負數格子][方向]
int g[N][N];
int direct[3][2] = {{0,-1}, {1,0}, {0,1}}; //left, down, right
int n, qk, ans, kase = 1;

void init(){
    ans = -INF;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            for(int k = 0; k < 10; k++){
                for(int m = 0; m < 5; m++)
                    dp[i][j][k][m] = -INF;
            }
        }
    }
    memset(visit, 0, sizeof(visit));
    memset(g, 0, sizeof(g));

    for(int i = 1; i <= n; i++){//輸入資料
        for(int j = 1; j <= n; j++){
            cin >> g[i][j];
        }
    }
}

void dfs(int x, int y, int cnt, int sum){
    if(cnt > qk) return;
    if(x == n && y == n){ //看是不是最大
        ans = max(sum, ans);
        return;
    }

    int mx, my;
    for(int k = 0; k < 3; k++){ //針對三個方向不斷遞迴
        mx = x + direct[k][0];
        my = y + direct[k][1];

        //判斷是否出界，visit[mx][my] 則是要避免節點先往左後往右，導致不斷循環
        //且不同方向、同個節點是不允許被重複使用
        if(mx <= 0 || mx > n || my <= 0 || my > n || visit[mx][my]) continue; //out of boarder

        //此節點以使用當前格子
        visit[mx][my] = 1;
        //如果現在節點權重比 dp 大才有延伸的必要性
        if(g[mx][my] >= 0 && sum + g[mx][my] > dp[mx][my][cnt][k]){
            dp[mx][my][cnt][k] = sum + g[mx][my];

            //cout << "mx my " << mx << " " << my << " " << dp[mx][my][cnt][k] << "\n";
            dfs(mx, my, cnt, sum+g[mx][my]);
        }
        else if(g[mx][my] < 0 && sum + g[mx][my] > dp[mx][my][cnt+1][k]){
            dp[mx][my][cnt+1][k] = sum + g[mx][my];
            dfs(mx, my, cnt+1, sum+g[mx][my]);
        }
        //此節點不再使用當前格子
        visit[mx][my] = 0;
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    while(cin >> n >> qk && (n+qk) != 0){
        init();

        visit[1][1] = 1;
        if(g[1][1] >= 0) dfs(1,1,0, g[1][1]); 
        if(g[1][1] < 0) dfs(1,1,1, g[1][1]); //出發點是負數，則一開始要記錄

        cout << "Case " << kase++ << ": ";
        if(ans == -INF) cout << "impossible\n";
        else cout << ans << "\n";
    }
    return 0;
}