ZeroJudge 解題筆記：l924. P.7 搜集寶藏 (Treasure)

作者：王一哲
日期：2025年5月25日



ZeroJudge 題目連結：l924. P.7 搜集寶藏 (Treasure)

解題想法

但是這題的記憶體限制很嚴格，如果先將所有格子的資料存進二維陣列，不論是用 Python 或 C++ 記憶體都不夠。如果改用滾動陣列節省記憶體，Python 還是無法通過，C++ 勉強可以過關。

Python 程式碼

寫法1，先將所有格子的資料存進二維串列。但是這題的記憶體限制很嚴格，我用 Python 解題在第 2、5、8、9、12、18 筆測資記憶體爆掉。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # 地圖 n*m
    grid = [list(map(int, input().split())) for _ in range(n)]  # 讀取地圖資料
    for i in range(1, n):  # 處理第 0 欄
        grid[i][0] += grid[i-1][0]
    for j in range(1, m):  # 處理第 0 列
        grid[0][j] += grid[0][j-1]
    for i in range(1, n):  # 處理 grid[1][1] ~ grid[n-1][m-1]
        for j in range(1, m):
            grid[i][j] += max(grid[i-1][j], grid[i][j-1])
    print(grid[n-1][m-1])  # 答案在 grid[n-1][m-1]

寫法2，用滾動陣列節省記憶體，結果第2筆測資就超時。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # 地圖 n*m
    pre = list(map(int, input().split()))  # 讀取第 0 列地圖資料
    for j in range(1, m):  # 處理第 0 列
        pre[j] += pre[j-1]
    for _ in range(1, n):  # 處理第 1 ~ n-1 列
        cur = list(map(int, input().split()))  # 讀取一列地圖資料
        cur[0] += pre[0]  # 處理第 0 欄
        for j in range(1, m):  # 依序更新第 1 ~ m-1 欄
            cur[j] += max(pre[j], cur[j-1])
        pre, cur = cur, pre  # 交換 pre, cur 的資料
    print(pre[m-1])  # 答案在 pre[n-1][m-1]

C++ 程式碼

寫法1，先將所有格子的資料存進二維陣列。但是這題的記憶體限制很嚴格，我用 C++ 解題在第 2、12 筆測資記憶體爆掉。

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int n, m;  // 地圖 n*m
    while(scanf("%d %d", &n, &m) != EOF) {
        int grid[n][m];  // 讀取地圖資料
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                scanf("%d", &grid[i][j]);
            }
        }
        for(int i=1; i<n; i++) grid[i][0] += grid[i-1][0];  // 處理第 0 欄
        for(int j=1; j<m; j++) grid[0][j] += grid[0][j-1];  // 處理第 0 列
        for(int i=1; i<n; i++) {  // 處理 grid[1][1] ~ grid[n-1][m-1]
            for(int j=1; j<m; j++) {
                grid[i][j] += max(grid[i-1][j], grid[i][j-1]);
            }
        }
        printf("%d\n", grid[n-1][m-1]);  // 答案在 grid[n-1][m-1]
    }
    return 0;
}

寫法2，用滾動陣列節省記憶體。使用時間約為 0.3 s，記憶體約為 288 kB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;  // 地圖 n*m
    while(scanf("%d %d", &n, &m) != EOF) {
        vector<int> pre (m);  // 讀取並處理第 0 列地圖資料
        scanf("%d", &pre[0]);
        for(int j=1; j<m; j++) {
            scanf("%d", &pre[j]);
            pre[j] += pre[j-1];
        }
        for(int i=1; i<n; i++) {  // 處理第 1 ~ n-1 列
            vector<int> cur (m);  // 讀取一列地圖資料
            scanf("%d", &cur[0]);  // 處理第 0 欄
            cur[0] += pre[0];
            for(int j=1; j<m; j++) {  // 依序更新第 1 ~ m-1 欄
                scanf("%d", &cur[j]);
                cur[j] += max(pre[j], cur[j-1]);
            }
            swap(pre, cur);  // 交換 pre, cur 的資料
        }
        printf("%d\n", pre[m-1]);  // 答案在 pre[m-1]
    }
    return 0;
}