ZeroJudge 解題筆記：a746. 画蛇添足

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


ZeroJudge 題目連結：a746. 画蛇添足

解題想法

這題的測資 2 有空行，如果用 Python 需要過濾掉空行，否則會出錯。而且這題的記憶體限制很嚴格，如果用 Python 直接産生 $(n+2) \times (n+2)$ 的二維串列會超過記憶體上限。

Python 程式碼

第3行是為了濾掉測資中的空行，但是這樣測試不會過，因為本題的記憶體限制很嚴格，在第 7 行産生 $(n+2) \times (n+2)$ 的二維串列時會超過記憶體上限。

import sys

lines = [line for line in sys.stdin.readlines() if line.strip()]
idx = 0

while idx < len(lines):
    n, m = map(int, lines[idx].split())
    idx += 1
    grid = [[" "]*(n+2) for _ in range(n+2)]
    for c in range(n+2):
        grid[0][c] = grid[n+1][c] = "-"
    for r in range(1, n+1):
        grid[r][0] = grid[r][n+1] = "|"
    ri, ci = map(int, lines[idx].split())
    idx += 1
    for _ in range(m-1):
        rf, cf = map(int, lines[idx].split())
        idx += 1
        if ri == rf:
            for c in range(min(ci, cf), max(ci, cf)+1):
                grid[ri][c] = "*"
        elif ci == cf:
            for r in range(min(ri, rf), max(ri, rf)+1):
                grid[r][ci] = "*"
        ri, ci = rf, cf
    for row in grid:
        sys.stdout.write("".join(row) + "\n")

先用 set 記錄要畫星號的座標，輸出答案時每次只産生一列，減少記憶體使用量。使用時間約為 0.3 s，記憶體約為 3.6 MB，通過測試。

import sys

lines = [line for line in sys.stdin.readlines() if line.strip()]
idx = 0

while idx < len(lines):
    n, m = map(int, lines[idx].split())
    idx += 1
    stars = set()
    ri, ci = map(int, lines[idx].split())
    idx += 1
    for _ in range(m-1):
        rf, cf = map(int, lines[idx].split())
        idx += 1
        if ri == rf:
            for c in range(min(ci, cf), max(ci, cf)+1):
                stars.add((ri, c))
        elif ci == cf:
            for r in range(min(ri, rf), max(ri, rf)+1):
                stars.add((r, ci))
        ri, ci = rf, cf
    sys.stdout.write("-"*(n+2) + "\n")
    for r in range(1, n+1):
        row = ["|"]
        for c in range(1, n+1):
            if (r, c) in stars: row.append("*")
            else: row.append(" ")
        row.append("|")
        sys.stdout.write("".join(row) + "\n")
    sys.stdout.write("-"*(n+2) + "\n")

C++ 程式碼

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

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    while(cin >> n >> m) {
        string spaces (n+2, ' ');  // n+2 個空格
        vector<string> grid (n+2, spaces);  // n+2 列，每列都是 n+2 個空格
        for(int c=0; c<n+2; c++) {
            grid[0][c] = '-';
            grid[n+1][c] = '-';
        }
        for(int r=1; r<n+1; r++) {
            grid[r][0] = '|';
            grid[r][n+1] = '|';
        }
        int ri, ci; cin >> ri >> ci;
        for(int i=0; i<m-1; i++) {
            int rf, cf; cin >> rf >> cf;
            if (ri == rf) {
                for(int c=min(ci, cf); c<=max(ci, cf); c++) {
                    grid[ri][c] = '*';
                }
            } else if (ci == cf) {
                for(int r=min(ri, rf); r<=max(ri, rf); r++) {
                    grid[r][ci] = '*';
                }
            }
            ri = rf; ci = cf;
        }
        for(string row : grid) cout << row << "\n";
    }
    return 0;
}

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

#include <iostream>
#include <string>
#include <set>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    while(cin >> n >> m) {
        set<pair<int, int>> stars;
        int ri, ci; cin >> ri >> ci;
        for(int i=0; i<m-1; i++) {
            int rf, cf; cin >> rf >> cf;
            if (ri == rf) {
                for(int c=min(ci, cf); c<=max(ci, cf); c++) stars.insert(make_pair(ri, c));
            } else if (ci == cf) {
                for(int r=min(ri, rf); r<=max(ri, rf); r++) stars.insert(make_pair(r, ci));
            }
            ri = rf; ci = cf;
        }
        string dash (n+2, '-');  // n+2 個 -
        cout << dash << "\n";
        for(int r=1; r<=n; r++) {
            string row (n+2, ' ');  // n+2 個空格
            row[0] = '|';
            row[n+1] = '|';
            for(int c=1; c<=n; c++) {
                pair<int, int> pos = {r, c};
                if (stars.find(pos) != stars.end()) row[pos.second] = '*';
            }
            cout << row << "\n";
        }
        cout << dash << "\n";
    }
    return 0;
}