ZeroJudge 解題筆記：m800. 辦公室 (Office)

作者：王一哲
日期：2025年6月1日



ZeroJudge 題目連結：m800. 辦公室 (Office)

解題想法

這題我沒有想到比較快的寫法。依序檢查每一格四周的格子比自己高或低的數量，將變化量儲存到另一個陣列，最後再更新每一格的值，重複以上的過程 k 次。

Python 程式碼

只能通過4筆測資然後就超時了。

import sys

for line in sys.stdin:
    h, w, k = map(int, line.split())  # 平面圖 h*w，共 k 天
    start = 0  # 一開始的加總 start
    grid = []  # 平面圖 grid
    for _ in range(h):  # 讀取 h 行資料
        grid.append(list(map(int, input().split())))
        start += sum(grid[-1])
    tmp = [0]*(h*w)  # 暫存變化量用的陣列，改成一維，節省記憶體
    for _ in range(k):  # 更新 k 次
        for r in range(h):  # 依序檢查每一格
            for c in range(w):
                tot, large, small = 0, 0, 0  # 四周共有 tot 格，比自己大的數量 large，比自己小的數量 small
                for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
                    nr, nc = r+dr, c+dc  # 要檢查的位置 (nr, nc)
                    if nr < 0 or nr >= h or nc < 0 or nc >= w: continue  # 如果 (nr, nc) 出界，找下一個
                    tot += 1  # 更新 tot
                    if grid[nr][nc] > grid[r][c]: large += 1  # 更新 large
                    elif grid[nr][nc] < grid[r][c]: small += 1  # 更新 small
                if 2*large > tot: tmp[r*w + c] = 1  # 如果 large 過半，tmp[r*w + c] 等於 1
                elif 2*small > tot: tmp[r*w + c] = -1  # 如果 small 過半，tmp[r*w + c] 等於 -1
                else: tmp[r*w + c] = 0  # 否則 tmp[r*w + c] 等於 0
        for r in range(h):  # 更新每一格的值
            for c in range(w):
                grid[r][c] += tmp[r*w + c]
    end = 0  # k 天後的加總
    for row in grid: end += sum(row)
    print(end-start)  # 印出答案

C++ 程式碼

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

#include <cstdio>
using namespace std;

int main() {
    int h, w, k;  // 平面圖 h*w，共 k 天
    int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};  // 四方位檢查用的位移量
    while(scanf("%d %d %d", &h, &w, &k) != EOF) {  // 讀取 h, w, k 直到沒有輸入為止
        int start = 0, grid[h][w];  // 一開始的加總 start，平面圖 grid
        for(int r=0; r<h; r++) {  // 依序讀取每格的值，計算 start
            for(int c=0; c<w; c++) {
                int n; scanf("%d", &n);
                start += n;
                grid[r][c] = n;
            }
        }
        int tmp[h*w];  // 暫存變化量用的陣列，改成一維，節省記憶體
        for(int d=0; d<k; d++) {  // 更新 k 次
            for(int r=0; r<h; r++) {  // 依序檢查每一格
                for(int c=0; c<w; c++) {
                    int tot = 0, large = 0, small = 0;  // 四周共有 tot 格，比自己大的數量 large，比自己小的數量 small
                    for(int i=0; i<4; i++) {  // 四方位檢查
                        int nr = r+dr[i], nc = c+dc[i];  // 要檢查的位置 (nr, nc)
                        if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;  // 如果 (nr, nc) 出界，找下一個
                        tot++;  // 更新 tot
                        if (grid[nr][nc] > grid[r][c]) large++;  // 更新 large
                        else if (grid[nr][nc] < grid[r][c]) small++;  // 更新 small
                    }
                    if (2*large > tot) tmp[r*w + c] = 1;  // 如果 large 過半，tmp[r*w + c] 等於 1
                    else if (2*small > tot) tmp[r*w + c] = -1;  // 如果 small 過半，tmp[r*w + c] 等於 -1
                    else tmp[r*w + c] = 0;  // 否則 tmp[r*w + c] 等於 0
                }
            }
            for(int r=0; r<h; r++) {  // 更新每一格的值
                for(int c=0; c<w; c++) {
                    grid[r][c] += tmp[r*w + c];
                }
            }
        }
        int end = 0;  // k 天後的加總
        for(int r=0; r<h; r++) {
            for(int c=0; c<w; c++) {
                end += grid[r][c];
            }
        }
        printf("%d\n", end-start);  // 印出答案
    }
    return 0;
}