ZeroJudge 解題筆記：g004. 社區熱門度 (Popularity)

作者：王一哲
日期：2025年3月21日



ZeroJudge 題目連結：g004. 社區熱門度 (Popularity)

解題想法

處理這種類型的題目時，我習慣在周圍或是最後面多加一些資料，可以避免在四方位檢查時出界。

Python 程式碼

可以先將答案存入另一個二維串列，使用時間約為 19 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    m, n = map(int, line.split())  # 地圖 m*n
    grid = [list(map(int, input().split())) + [0] for _ in range(m)]  # 地圖資料，最後加上 0
    grid.append([0]*(n+1))  # 最後加上 n+1 個 0
    ans = [grid[r][:-1] for r in range(m)]  # 儲存答案用的二維串列
    for r in range(m):  # 依序掃過每一格
        for c in range(n):
            if grid[r][c] != 0: continue  # 如果 (r, c) 這個不等於 0，找下一格
            cnt, tot = 0, 0  # 右下左上 4 格非 0 的格子數量，熱門度加總
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 檢查周圍 4 格
                v = grid[r+dr][c+dc]
                if v != 0:
                    cnt += 1; tot += v
            if tot != 0: ans[r][c] = tot//cnt  # 如果 tot 不等於 0，更新 ans[r][c]
    for row in ans: print(*row)  # 印出答案

也可以直接將答案印出來，使用時間約為 35 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    m, n = map(int, line.split())  # 地圖 m*n
    grid = [list(map(int, input().split())) + [0] for _ in range(m)]  # 地圖資料，最後加上 0
    grid.append([0]*(n+1))  # 最後加上 n+1 個 0
    for r in range(m):  # 依序掃過每一格
        for c in range(n):
            if grid[r][c] != 0:  # 如果 (r, c) 這個不等於 0，印出此格，找下一格
                print(grid[r][c], end="\n" if c == n-1 else " ")
                continue
            cnt, tot = 0, 0  # 右下左上 4 格非 0 的格子數量，熱門度加總
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 檢查周圍 4 格
                v = grid[r+dr][c+dc]
                if v != 0:
                    cnt += 1; tot += v
            if tot != 0:  # 如果 tot 不等於 0，印出 tot//cnt
                print(tot//cnt, end="\n" if c == n-1 else " ")
            else:  # 如果 tot 不等於 0，印出 0
                print(0, end="\n" if c == n-1 else " ") 

C++ 程式碼

只用 scnaf, printf, array，使用時間約為 2 ms，記憶體約為 92 kB，通過測試。

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

int main() {
    int m, n;  // 地圖 m*n
    int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};  // 檢查周圍 4 格用的位移量
    while(scanf("%d %d", &m, &n) != EOF) {
        int grid[m+2][n+2];  // 地圖，四周加一圈 0
        memset(grid, 0, sizeof(grid));
        for(int r=1; r<=m; r++) {  // 讀取地圖資料
            for(int c=1; c<=n; c++) {
                int v; scanf("%d", &v);
                grid[r][c] = v;
            }
        }
        for(int r=1; r<=m; r++) {  // 依序掃過每一格
            for(int c=1; c<=n; c++) {
                if (grid[r][c] != 0) {  // 如果 (r, c) 這個不等於 0，印出此格，找下一格
                    if (c == n) printf("%d\n", grid[r][c]);
                    else printf("%d ", grid[r][c]);
                    continue;
                }
                int cnt = 0, tot = 0;  // 右下左上 4 格非 0 的格子數量，熱門度加總
                for(int i=0; i<4; i++) {  // 檢查周圍 4 格
                    int v = grid[r+dr[i]][c+dc[i]];
                    if (v != 0) {
                        cnt++; tot += v;
                    }
                }
                if (tot != 0) {  // 如果 tot 不等於 0，印出 tot/cnt
                    if (c == n) printf("%d\n", tot/cnt);
                    else printf("%d ", tot/cnt);
                } else {  // 如果 tot 等於 0，印出 0
                    if (c == n) printf("0\n");
                    else printf("0 ");
                }
            }
        }
    }
    return 0;
}

改用 cin, cout, vector，使用時間約為 3 ms，記憶體約為 328 kB，通過測試。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n;  // 地圖 m*n
    int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};  // 檢查周圍 4 格用的位移量
    while(cin >> m >> n) {
        vector<vector<int>> grid (m+2, vector<int> (n+2, 0));  // 地圖，四周加一圈 0
        for(int r=1; r<=m; r++) {  // 讀取地圖資料
            for(int c=1; c<=n; c++) {
                cin >> grid[r][c];
            }
        }
        for(int r=1; r<=m; r++) {  // 依序掃過每一格
            for(int c=1; c<=n; c++) {
                if (grid[r][c] != 0) {  // 如果 (r, c) 這個不等於 0，印出此格，找下一格
                    cout << grid[r][c] << " \n"[c == n];
                    continue;
                }
                int cnt = 0, tot = 0;  // 右下左上 4 格非 0 的格子數量，熱門度加總
                for(int i=0; i<4; i++) {  // 檢查周圍 4 格
                    int v = grid[r+dr[i]][c+dc[i]];
                    if (v != 0) {
                        cnt++; tot += v;
                    }
                }
                if (tot != 0) {  // 如果 tot 不等於 0，印出 tot/cnt
                    cout << tot/cnt << " \n"[c == n];
                } else {  // 如果 tot 等於 0，印出 0
                    cout << 0 << " \n"[c == n];
                }
            }
        }
    }
    return 0;
}