ZeroJudge 解題筆記：f513. 舉旗遊戲 (Flag)

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



ZeroJudge 題目連結：f513. 舉旗遊戲 (Flag)

解題想法

這題如果在周圍加上 0 作為哨兵，可以在檢查周圍 8 格時不需要考慮是否出界，程式碼會比較簡單。由於 Python 的串列索引值 -1 會對應到最後一項，不需要圍一整圈，只要圍最右側、最下方即可。

Python 程式碼

使用時間約為 39 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 作為哨兵
    tot = 0  # 淘汰人數
    for r in range(m):  # 依序檢查每個人
        for c in range(n):
            a = grid[r][c]  # 這個人的顏色 a
            out = True  # 是否淘汰
            for dr, dc in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):  # 檢查周圍 8 格
                nr, nc = r+dr, c+dc  # 要檢查的格子 (nr, nc)
                if grid[nr][nc] == a:  # 如果 (nr, nc) 的顏色與 a 相同
                    out = False; break  # 不會淘汰，中止迴圈
            if out: tot += 1  # 如果淘汰了，tot 加 1
    print(tot)

C++ 程式碼

用 array 儲存地圖資料，使用時間約為 2 ms，記憶體約為 348 kB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n;  // 地圖 m*n
    while(cin >> m >> n) {
        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++) cin >> grid[r][c];
        }
        int tot = 0;  // 淘汰人數
        int dr[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dc[8] = {1, 1, 0, -1, -1, -1, 0, 1};  // 檢查周圍 8 格的位移量
         for(int r=1; r<=m; r++) {  // 依序檢查每個人
            for(int c=1; c<=n; c++) {
                int a = grid[r][c];  // 這個人的顏色 a
                bool out = true;  // 是否淘汰
                for(int i=0; i<8; i++) {  // 檢查周圍 8 格
                    int nr = r+dr[i], nc = c+dc[i];  // 要檢查的格子 (nr, nc)
                    if (grid[nr][nc] == a) {  // 如果 (nr, nc) 的顏色與 a 相同
                        out = false; break;  // 不會淘汰，中止迴圈
                    }
                }
                if (out) tot++;  // 如果淘汰了，tot 加 1
            }
        }
        cout << tot << "\n";
    }
    return 0;
}

用 vector 儲存地圖資料，使用時間約為 2 ms，記憶體約為 344 kB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n;  // 地圖 m*n
    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];
        }
        int tot = 0;  // 淘汰人數
        int dr[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dc[8] = {1, 1, 0, -1, -1, -1, 0, 1};  // 檢查周圍 8 格的位移量
         for(int r=1; r<=m; r++) {  // 依序檢查每個人
            for(int c=1; c<=n; c++) {
                int a = grid[r][c];  // 這個人的顏色 a
                bool out = true;  // 是否淘汰
                for(int i=0; i<8; i++) {  // 檢查周圍 8 格
                    int nr = r+dr[i], nc = c+dc[i];  // 要檢查的格子 (nr, nc)
                    if (grid[nr][nc] == a) {  // 如果 (nr, nc) 的顏色與 a 相同
                        out = false; break;  // 不會淘汰，中止迴圈
                    }
                }
                if (out) tot++;  // 如果淘汰了，tot 加 1
            }
        }
        cout << tot << "\n";
    }
    return 0;
}