ZeroJudge 解題筆記：f680. 色塊數量

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


ZeroJudge 題目連結：f680. 色塊數量

解題想法

標準的 BFS 題目。

Python 程式碼

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

from collections import deque

n = int(input())  # 地圖 n*n，最右側、最下方加上 0 作為哨兵
grid = [list(map(int, input().split())) + [0] for _ in range(n)]
grid.append([0]*(n+1))
### BFS ###
cnt = 0  # 色塊數量
for i in range(n):  # 依序掃過每一格
    for j in range(n):
        if grid[i][j] == 0: continue  # 如果此格是 0 找下一格
        color = grid[i][j]  # 此格的顏色
        grid[i][j] = 0  # 此格設定為 0
        que = deque([(i, j)])  # (i, j) 加入待走訪佇列
        cnt += 1  # 色塊數量加 1
        while que:  # 如果 que 還有資料繼續執行
            r, c = que.popleft()  # 從 que 開頭讀取並移除資料
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
                nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                if grid[nr][nc] != color: continue  # 如果此格顏色不一樣，找下一格
                grid[nr][nc] = 0  # 此格設定為 0
                que.append((nr, nc))  # (nr, nr) 加入待走訪佇列
### End of BFS ###
print(cnt)  # 印出答案

C++ 程式碼

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

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

int main() {
    int n; scanf("%d", &n);  // 地圖 n*n，四周加上 0 作為哨兵
    int grid[n+2][n+2];
    memset(grid, 0, sizeof(grid));
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) scanf("%d", &grid[i][j]);
    }
    /* BFS */
    int cnt = 0, dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};  // 色塊數量
    for(int i=1; i<=n; i++) {  // 依序掃過每一格
        for(int j=1; j<=n; j++) {
            if (grid[i][j] == 0) continue;  // 如果此格是 0 找下一格
            int color = grid[i][j];  // 此格的顏色
            grid[i][j] = 0;  // 此格設定為 0
            queue<pair<int, int>> que; que.push(make_pair(i, j));  // (i, j) 加入待走訪佇列
            cnt++;  // 色塊數量加 1
            while(!que.empty()) {  // 如果 que 還有資料繼續執行
                int r = que.front().first, c = que.front().second; que.pop();  // 從 que 開頭讀取並移除資料
                for(int k=0; k<4; k++) {  // 四方向檢查
                    int nr = r+dr[k], nc = c+dc[k];  // 要檢查 (nr, nc)
                    if (grid[nr][nc] != color) continue;  // 如果此格顏色不一樣，找下一格
                    grid[nr][nc] = 0;  // 此格設定為 0
                    que.push(make_pair(nr, nc));  // (nr, nr) 加入待走訪佇列
                }
            }
        }
    }
    /* End of BFS */
    printf("%d\n", cnt);  // 印出答案
    return 0;
}