ZeroJudge 解題筆記：l921. P.4 草圖 (Sketch)

作者：王一哲
日期：2025年5月23日



ZeroJudge 題目連結：l921. P.4 草圖 (Sketch)

解題想法

因為這題要檢查的範圍比較大，要加兩層題目沒有用到的符號作為哨兵，避免走訪時出界。

Python 程式碼

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

import sys

# 右、右下、下、左下、左、左上、上、右上，距離2格，距離1格
two = ((0, 2), (2, 2), (2, 0), (2, -2), (0, -2), (-2, -2), (-2, 0), (-2, 2))
one = ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1))
sym = ('-', '\\', '|', '/', '-', '\\', '|', '/')

for line in sys.stdin:
    R = int(line)  # 圖形 (2*R - 1) * (2*R - 1)，要加上點之間的格子
    grid = [['#']*(2*R - 1) + ['!']*2 for _ in range(2*R - 1)]  # 圖形先填入 #，最後以 ! 作為哨兵
    grid += [['!']*(2*R +1), ['!']*(2*R +1)]  # 最下方加 2 列 ! 作為哨兵
    N = int(input())  # N 個點
    ps = []  # 點的位置
    for _ in range(N):  # 讀取 N 行資料
        r, c = map(int, input().split())  # 座標 (r, c)
        r *= 2; c *= 2  # 配合 grid 的維度要乘以 2
        ps.append((r, c))  # (r, c) 加入 ps
        grid[r][c] = '&'  # grid[r][c] 標記成 &
    for r, c in ps:  # 從 ps 依序取出點的座標
        for i in range(8):  # 8 方向檢查
            nr, nc = r+two[i][0], c+two[i][1]  # 要檢查的座標 (nr, nc)，距離 2 格
            if grid[nr][nc] == '&':  # 如果 grid[nr][nc] 是 &
                cr, cc = r+one[i][0], c+one[i][1]  # 距離 1 格的位置
                if grid[cr][cc] == '#':  # 如果 grid[cr][cc] 還沒有標記
                    grid[cr][cc] = sym[i]
                elif ((i == 3 or i == 7) and grid[cr][cc] == '\\') or \
                     ((i == 1 or i == 5) and grid[cr][cc] == '/'):
                    grid[cr][cc] = 'X'
    for row in grid[:2*R - 1]: print(''.join(row[:2*R - 1]))

C++ 程式碼

寫法1，用一維字串陣列儲存地圖資料，速度會比較慢。使用時間約為 4 ms，記憶體約為 348 kB，通過測試。

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

int main() {
    // 右、右下、下、左下、左、左上、上、右上，距離2格，距離1格
    int two[8][2] = {{0, 2}, {2, 2}, {2, 0}, {2, -2}, {0, -2}, {-2, -2}, {-2, 0}, {-2, 2}};
    int one[8][2] = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
    char sym[8] = {'-', '\\', '|', '/', '-', '\\', '|', '/'};
    int R;  // 圖形 (2*R + 3) * (2*R + 3)，要加上點之間的格子以及四周兩圈的哨兵
    while(cin >> R) {
        string grid[2*R + 3];  // 圖形四周要加兩圈 ! 作為哨兵
        for(int i=0; i<2*R+3; i++) {  // 處理最上面、最下面兩列
            grid[0] += '!'; grid[1] += '!'; grid[2*R+1] += '!'; grid[2*R+2] += '!';
        }
        for(int i=2; i<2*R+1; i++) {  // 處理第 2 ~ 2*R 列，圖形先填入 #，頭尾各加入兩個 ! 作為哨兵
            grid[i] = "!!";
            for(int j=2; j<2*R+1; j++) grid[i] += '#';
            grid[i] += "!!";
        }
        int N; cin >> N;  // N 個點
        int ps[N][2];  // 點的位置
        for(int i=0; i<N; i++) {  // 讀取 N 行資料
            int r, c; cin >> r >> c;  // 座標 (r, c)
            r = 2*r + 2; c = 2*c + 2;  // 配合 grid 的維度要乘以 2 再加 2
            ps[i][0] = r; ps[i][1] = c;  // (r, c) 加入 ps
            grid[r][c] = '&';  // grid[r][c] 標記成 &
        }
        for(int i=0; i<N; i++) {  // 從 ps 依序取出點的座標
            int r = ps[i][0], c = ps[i][1];
            for(int j=0; j<8; j++) {  // 8 方向檢查
                int nr = r+two[j][0], nc = c+two[j][1];  // 要檢查的座標 (nr, nc)，距離 2 格
                if (grid[nr][nc] == '&') {  // 如果 grid[nr][nc] 是 &
                    int cr = r+one[j][0], cc = c+one[j][1];  // 距離 1 格的位置
                    if (grid[cr][cc] == '#') {  // 如果 grid[cr][cc] 還沒有標記
                        grid[cr][cc] = sym[j];
                    } else if (((j == 3 || j == 7) && grid[cr][cc] == '\\') ||
                               ((j == 1 || j == 5) && grid[cr][cc] == '/')) {
                        grid[cr][cc] = 'X';
                    }
                }
            }
        }
        for(int i=2; i<2*R+1; i++) cout << grid[i].substr(2, 2*R-1) << "\n";
    }
    return 0;
}

寫法2，用二維字元陣列儲存地圖資料，周圍兩圈可以不需要存入資料，速度快很多。使用時間約為 3 ms，記憶體約為 104 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    // 右、右下、下、左下、左、左上、上、右上，距離2格，距離1格
    int two[8][2] = {{0, 2}, {2, 2}, {2, 0}, {2, -2}, {0, -2}, {-2, -2}, {-2, 0}, {-2, 2}};
    int one[8][2] = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
    char sym[8] = {'-', '\\', '|', '/', '-', '\\', '|', '/'};
    int R;  // 圖形 (2*R + 3) * (2*R + 3)，要加上點之間的格子以及四周兩圈的哨兵
    while(scanf("%d", &R) != EOF) {
        char grid[2*R + 3][2*R + 3];  // 圖形四周要加兩圈空字元避免 8 方向檢查時出界
        for(int i=2; i<2*R+1; i++) {  // 處理第 2 ~ 2*R 列，圖形先填入 #
            for(int j=2; j<2*R+1; j++) grid[i][j] = '#';
        }
        int N; scanf("%d", &N);  // N 個點
        int ps[N][2];  // 點的位置
        for(int i=0; i<N; i++) {  // 讀取 N 行資料
            int r, c; scanf("%d %d", &r, &c);  // 座標 (r, c)
            r = 2*r + 2; c = 2*c + 2;  // 配合 grid 的維度要乘以 2 再加 2
            ps[i][0] = r; ps[i][1] = c;  // (r, c) 加入 ps
            grid[r][c] = '&';  // grid[r][c] 標記成 &
        }
        for(int i=0; i<N; i++) {  // 從 ps 依序取出點的座標
            int r = ps[i][0], c = ps[i][1];
            for(int j=0; j<8; j++) {  // 8 方向檢查
                int nr = r+two[j][0], nc = c+two[j][1];  // 要檢查的座標 (nr, nc)，距離 2 格
                if (grid[nr][nc] == '&') {  // 如果 grid[nr][nc] 是 &
                    int cr = r+one[j][0], cc = c+one[j][1];  // 距離 1 格的位置
                    if (grid[cr][cc] == '#') {  // 如果 grid[cr][cc] 還沒有標記
                        grid[cr][cc] = sym[j];
                    } else if (((j == 3 || j == 7) && grid[cr][cc] == '\\') ||
                               ((j == 1 || j == 5) && grid[cr][cc] == '/')) {
                        grid[cr][cc] = 'X';
                    }
                }
            }
        }
        for(int i=2; i<2*R+1; i++) {
            for(int j=2; j<2*R+1; j++) printf("%c", grid[i][j]);
            puts("");
        }
    }
    return 0;
}