ZeroJudge 解題筆記：i177. 小畫家 (Painter)

作者：王一哲
日期：2025年11月16日


ZeroJudge 題目連結：i177. 小畫家 (Painter)

解題想法

這題用 BFS ，我習慣在旁邊加一圈哨兵，這樣可以不需要檢查是否出界。

Python 程式碼

加哨兵，不需要檢查是否出界，使用時間約為 0.4 s，記憶體約為 14.8 MB，通過測試。

from collections import deque

h, w, si, sj, z = map(int, input().split())
grid = [list(map(int, input().split())) + [-1] for _ in range(h)]
grid.append([-1]*(w+1))
color = grid[si-1][sj-1]
if color != z:
    que = deque([(si-1,sj-1)])
    grid[si-1][sj-1] = z
    while que:
        r, c = que.popleft()
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            nr, nc = r+dr, c+dc
            if grid[nr][nc] == color:
                grid[nr][nc] = z
                que.append((nr, nc))
for row in grid[:h]: print(*row[:w])

不加哨兵，要檢查是否出界，使用時間約為 0.5 s，記憶體約為 15.2 MB，通過測試。

from collections import deque

h, w, si, sj, z = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(h)]
color = grid[si-1][sj-1]
if color != z:
    que = deque([(si-1,sj-1)])
    grid[si-1][sj-1] = z
    while que:
        r, c = que.popleft()
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            nr, nc = r+dr, c+dc
            if 0 <= nr < h and 0 <= nc < w and grid[nr][nc] == color:
                grid[nr][nc] = z
                que.append((nr, nc))
for row in grid: print(*row)

C++ 程式碼

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

#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;

int main() {
    int h, w, si, sj, z;  // 圖的維度 h*w，起點位置 (si, sj)，填入顏色 z
    scanf("%d %d %d %d %d", &h, &w, &si, &sj, &z);
    int grid[h+2][w+2];  // 二維陣列，周圍加一圈哨兵
    memset(grid, -1, sizeof(grid));  // 全部設為 -1
    for(int r=1; r<=h; r++) {  // 讀取每格的顏色
        for(int c=1; c<=w; c++) scanf("%d", &grid[r][c]);
    }
    int color = grid[si][sj];  // 起點位置的顏色
    if (color != z) {  // 如果 color 不等於 z 才需要跑底下的程式碼
        queue<pair<int, int>> que;  // 待走訪佇列
        que.push(make_pair(si, sj));  // que 先加入 (si, sj)
        grid[si][sj] = z;  // 此格的顏色改成 z
        int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};  // 四方位檢查用的位移量
        while(!que.empty()) {  // BFS，持續執行直到 que 沒有資料為止
            int r = que.front().first, c = que.front().second;  // 目前走訪的格子 (r, c)
            que.pop();  // 移除 que 最前面的資料
            for(int i=0; i<4; i++) {  // 四方位檢查
                int nr = r+dr[i], nc = c+dc[i];  // 檢查格子 (nr, nc)
                if (grid[nr][nc] == color) {  // 如果此格等於 color
                    grid[nr][nc] = z;  // 此格改成 z
                    que.push(make_pair(nr, nc));  // (nr, nc) 加入 que
                }
            }
        }
    }
    for(int r=1; r<=h; r++) {  // 印出修改後的格子
        for(int c=1; c<w; c++) printf("%d ", grid[r][c]);
        printf("%d\n", grid[r][w]);
    }
    return 0;
}