ZeroJudge 解題筆記：e971. 2. 梗圖著色 (Coloring)

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



ZeroJudge 題目連結：e971. 2. 梗圖著色 (Coloring)

解題想法

只要記錄前一個 1 的位置就好，不需要用到 queue。

Python 程式碼

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

m, n = map(int, input().split())  # 圖的高度 m、寬度 n
for _ in range(m):  # 讀取 m 行資料
    arr = list(map(int, input().split()))  # 一行圖形資料
    pre = -1  # 前一個 1 的位置，預設為 -1
    for i, a in enumerate(arr):  # 由 arr 依序讀取數值 a、索引值 i
        if a == 1:  # 如果 a 等於 1
            if pre != -1:  # 如果 pre 不等於 -1
                for j in range(pre+1, i): arr[j] = 1 # 將 [pre+1, i-1] 之間都設定為 1
                pre = -1  # pre 重設為 -1
            else: pre = i  # 如果 pre 等於 -1，pre 設定為 i
    print(*arr)  # 印出這行塗色後的結果

C++ 程式碼

使用時間約為 6 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n; cin >> m >> n;  // 圖的高度 m、寬度 n
    for(int i=0; i<m; i++) {  // 讀取 m 行資料
        int arr[n] = {0}, pre = -1;  // 一行圖形資料，前一個 1 的位置，預設為 -1
        for(int j=0, a; j<n; j++) {  // 讀取 n 個數值 a
            cin >> a; arr[j] = a;  // 讀取圖形資料
            if (a == 1) {  // 如果 a 等於 1
                if (pre != -1) {  // 如果 pre 不等於 -1
                    for(int k=pre+1; k<j; k++) arr[k] = 1;  // 將 [pre+1, i-1] 之間都設定為 1
                    pre = -1;  // pre 重設為 -1
                } else pre = j;  // 如果 pre 等於 -1，pre 設定為 j
            }
        }
        for(int j=0; j<n; j++) cout << arr[j] << " \n"[j == n-1];  // 印出這行塗色後的結果
    }
    return 0;
}