ZeroJudge 解題筆記：k931. P8. 切割蜂蜜 (Honey)

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



ZeroJudge 題目連結：k931. P8. 切割蜂蜜 (Honey)

解題想法

這題有 3 個重點：

1. 要設計儲存六角形蜂巢資料的方式，我是用二維串列，偶數列的欄位為 1, 3, 5, ...，奇數列的欄位為 0, 2, 4, ...，這個寫法的優點是讀取資料時索引值比較好寫，缺點是會浪費接近一半的二維串列空間。
2. 用動態規畫計算從左到右切割到每一格時最小的累積損失量，取這一格的左上、左側、左下之中的最小值，再加上這格原來的值。
3. 為了避免檢查邊界值要寫一堆 if，我選擇在四周 (C++) 或是最右側、最下方 (Python) 加上正無窮大的值當作哨兵，缺點是要多花一點記憶體。

經過測試，這個寫法在目前通過測試的人當中，C++ 及 Python 使用的時間都最短，可能其他人都很認真地檢查是否出界吧！

Python 程式碼

使用時間約為 1.1 s，記憶體約為 26.7 MB，通過測試。

import sys

oo = float('inf')
for line in sys.stdin:
    H, W = map(int, line.split())  # 晶格的高與寬
    grid = [[-1]*(2*W+2) for _ in range(H)]  # 晶格 (H+1)*(2*W+2)
    grid.append([oo]*(2*W+2))  # 最下方補一列 oo
    for r in range(H):  # 讀取 H 行資料
        row = list(map(int, input().split()))
        if r%2 == 0:  # 如果是偶數列，欄位為 1, 3, 5, ..., 2*W - 1
            for i, v in enumerate(row):  # 索引值 i，數值 v
                grid[r][2*i+1] = v
            grid[r][2*W] = grid[r][2*W+1] = oo  # 最後面補上 oo 當作哨兵
        else:  # 如果是奇數列，欄位為 0, 2, 4, ..., 2*W
            for i, v in enumerate(row):  # 索引值 i，數值 v
                grid[r][2*i] = v
            grid[r][2*W+1] = oo  # 最後面補上 oo 當作哨兵
    # 動態規畫，grid[r][c] 改成到這格損失的值，加上左上、左側、左下最小值
    for c in range(2, 2*W+1):  # 依序掃過第 2 ~ 2*W 欄
        if c%2 == 0:  # 如果是偶數欄，列為 1, 3, 5, ...
            for r in range(1, H, 2):
                grid[r][c] += min(grid[r-1][c-1], grid[r][c-2], grid[r+1][c-1])
        else:  # 如果是奇數欄，列為 0, 2, 4, ...
            for r in range(0, H, 2):
                grid[r][c] += min(grid[r-1][c-1], grid[r][c-2], grid[r+1][c-1])
    # 找出答案，在每一列的最後一格，不含 oo
    ans = oo  # 答案預設為最大值
    for r in range(H):  # 依序掃過每一列
        if r%2 == 0: ans = min(ans, grid[r][2*W-1])  # 如果是偶數列
        else: ans = min(ans, grid[r][2*W])   # 如果是奇數列
    print(ans)

C++ 程式碼

使用時間約為 71 ms，記憶體約為 3.9 MB，通過測試。

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

const int oo = 1E9 + 1;

int main() {
    int H, W;  // 晶格的高與寬
    while(scanf("%d %d", &H, &W) != EOF) {
        int grid[H+2][2*W+2];  // 晶格 (H+2)*(2*W+2)
        memset(grid, -1, sizeof(grid));  // 先填入 -1
        for(int c=0; c<2*W+2; c++) {
            grid[0][c] = oo;  // 最上方為一列 oo
            grid[H+1][c] = oo;  // 最下方為一列 oo
        }
        for(int r=1; r<=H; r++) {  // 讀取 H 行資料
            if (r%2 == 1) {  // 如果是奇數列，欄位為 1, 3, 5, ..., 2*W - 1
                for(int i=0; i<W; i++) {  // 索引值 i
                    scanf("%d", &grid[r][2*i+1]);
                }
                grid[r][2*W] = grid[r][2*W+1] = oo;  // 最後面補上 oo 當作哨兵
            } else {  // 如果是偶數列，欄位為 0, 2, 4, ..., 2*W
                for(int i=0; i<=W; i++) {  // 索引值 i
                    scanf("%d", &grid[r][2*i]);
                }
                grid[r][2*W+1] = oo;  // 最後面補上 oo 當作哨兵
            }
        }
        // 動態規畫，grid[r][c] 改成到這格損失的值，加上左上、左側、左下最小值
        for(int c=2; c<2*W+1; c++) {  // 依序掃過第 2 ~ 2*W 欄
            if (c%2 == 0) {  // 如果是偶數欄，列為 2, 4, 6, ...
                for(int r=2; r<=H; r+=2) {
                    grid[r][c] += min(grid[r-1][c-1], min(grid[r][c-2], grid[r+1][c-1]));
                }
            } else {  // 如果是奇數欄，列為 1, 3, 4, ...
                for(int r=1; r<=H; r+=2) {
                    grid[r][c] += min(grid[r-1][c-1], min(grid[r][c-2], grid[r+1][c-1]));
                }
            }
        }
        // 找出答案，在每一列的最後一格，不含 oo
        int ans = oo;  // 答案預設為最大值
        for(int r=1; r<=H; r++) {  // 依序掃過每一列
            if (r%2 == 0) ans = min(ans, grid[r][2*W]);  // 如果是偶數列
            else ans = min(ans, grid[r][2*W-1]);   // 如果是奇數列
        }
        printf("%d\n", ans);
    }
    return 0;
}