日期：2026年10月19日
ZeroJudge 題目連結：f435.10267-Graphical Editor
解題想法
這題要模擬圖片編輯的操作過程，共有 8 個操作指令，雖然每個部分都不難，但是寫起來很長。指令開頭皆為一個大寫英文字母，後面再接上整數或字母。指令及功能分別為
- I M N：創造 $M \times N$ 的表格且每個像素的顏色為大寫英文字母 O。需要特別注意，題目的軸方向不一樣，這裡指的是表格有 N 列、M 欄。可以用二維陣列或是 C++ vector 搭配 string 儲存表格。
- C：使目前的表格顏色全為大寫英文字母 O，可以用迴圈或是 C++ vector.assign 處理。
- L X Y C：使 $(X,Y)$ 的像素顏色為 C。需要特別注意，題目的軸方向不一樣，而且是從 1 開始計算位置，這裡指的是二維陣列索引值 $[Y - 1][X - 1]$ 的格子。
- V X Y1 Y2 C：使 $(X, Y1) \dots (X, Y2)$ 的顏色為 C。需要特別注意，題目的軸方向不一樣，而且是從 1 開始計算位置，這裡指的是二維陣列索引值 $[Y1 - 1][X]$ 到 $[Y2 - 1][X]$ 的格子。
- H X1 X2 Y C：使 $(X1, Y) \dots (X2, Y)$ 的顏色為 C。需要特別注意，題目的軸方向不一樣，而且是從 1 開始計算位置，這裡指的是二維陣列索引值 $[Y][X1 - 1]$ 到 $[Y][X2 - 1]$ 的格子。
- K X1 Y1 X2 Y2 C：使由 $(X1, Y1)$ 為左上角、$(X2, Y2)$ 為右下角組成的矩形中所有的像素顏色為 C，可以用二層 for 迴圈處理。需要特別注意，題目的軸方向不一樣，而且是從 1 開始計算位置，這裡指的是二維陣列索引值 $[Y1 - 1][X1 - 1]$ 到 $[Y2 - 1][X2 - 1]$ 的格子。
- F X Y C：使 $(X, Y)$ 附近與它同顏色的像素顏色為 C，可以用 BFS 處理。需要特別注意，如果這格的顏色與 C 相同，不需要處理。題目的軸方向不一樣，而且是從 1 開始計算位置，這裡指的是二維陣列索引值 $[Y - 1][X - 1]$ 的格子。
- S Name：輸出 Name 之後輸出目前的表格。
- X：停止操作
Python 程式碼
使用時間約為 0.2 s，記憶體約為 11.4 MB，通過測試。
def solve():
import sys
from collections import deque
result = []
data = sys.stdin.read().split()
ptr = 0
graph = [] # 圖片
m, n = 0, 0 # 圖片尺寸 n 列 m 欄
while ptr < len(data):
op = data[ptr]
ptr += 1
if op == "I": # 建立 n 列 m 欄的圖片，內容皆為 O
m = int(data[ptr])
n = int(data[ptr + 1])
ptr += 2
graph = [["O"] * m for _ in range(n)]
elif op == "C": # 重置 n 列 m 欄的圖片，內容皆為 O
graph = [["O"] * m for _ in range(n)]
elif op == "L": # 改變 graph[y][x] 為指定的顏色
x = int(data[ptr]) - 1
y = int(data[ptr + 1]) - 1
ch = data[ptr + 2]
ptr += 3
graph[y][x] = ch
elif op == "V": # 改變 graph[y1][x] ~ graph[y2][x] 為指定的顏色
x = int(data[ptr]) - 1
y1 = int(data[ptr + 1]) - 1
y2 = int(data[ptr + 2]) - 1
ch = data[ptr + 3]
ptr += 4
for r in range(y1, y2 + 1):
graph[r][x] = ch
elif op == "H": # 改變 graph[y][x1] ~ graph[y][x2] 為指定的顏色
x1 = int(data[ptr]) - 1
x2 = int(data[ptr + 1]) - 1
y = int(data[ptr + 2]) - 1
ch = data[ptr + 3]
ptr += 4
graph[y][x1 : x2 + 1] = [ch] * (x2 - x1 + 1)
elif op == "K": # 改變 graph[y1][x1] ~ graph[y2][x2] 的矩形區域為指定的顏色
x1 = int(data[ptr]) - 1
y1 = int(data[ptr + 1]) - 1
x2 = int(data[ptr + 2]) - 1
y2 = int(data[ptr + 3]) - 1
ch = data[ptr + 4]
ptr += 5
for r in range(y1, y2 + 1):
for c in range(x1, x2 + 1):
graph[r][c] = ch
elif op == "F": # 將 graph[y][x] 及相鄰同色的格子改為指定的顏色
x = int(data[ptr]) - 1
y = int(data[ptr + 1]) - 1
ch = data[ptr + 2]
ptr += 3
target = graph[y][x] # 目標顏色
if target == ch: continue # 目標顏色與新的顏色相同，不需要改變
graph[y][x] = ch
que = deque([(y, x)])
while que: # BFS
r, c = que.popleft()
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and graph[nr][nc] == target:
graph[nr][nc] = ch
que.append((nr, nc))
elif op == "S": # 儲存圖片，印出檔名及目前的圖片
name = data[ptr]
result.append(f"{name}\n")
for row in graph:
res = "".join(map(str, row)) + "\n"
result.append(res)
elif op == "X": # 結束操作
continue
# 輸出答案
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
先開好 graph 為題目預設的最大尺寸 $250 \times 250$，之後只重設指定的範圍。使用時間約為 0.2 s，記憶體約為 11.2 MB，通過測試。
def solve():
import sys
from collections import deque
result = []
data = sys.stdin.read().split()
ptr = 0
graph = [["O"] * 250 for _ in range(250)] # 圖片，直接開好預設的最大尺寸 250*250
m, n = 0, 0 # 圖片尺寸 n 列 m 欄
while ptr < len(data):
op = data[ptr]
ptr += 1
if op == "I": # 建立 n 列 m 欄的圖片，內容皆為 O
m = int(data[ptr])
n = int(data[ptr + 1])
ptr += 2
for r in range(n):
graph[r][:m] = ["O"] * m
elif op == "C": # 重置 n 列 m 欄的圖片，內容皆為 O
for r in range(n):
graph[r][:m] = ["O"] * m
elif op == "L": # 改變 graph[y][x] 為指定的顏色
x = int(data[ptr]) - 1
y = int(data[ptr + 1]) - 1
ch = data[ptr + 2]
ptr += 3
graph[y][x] = ch
elif op == "V": # 改變 graph[y1][x] ~ graph[y2][x] 為指定的顏色
x = int(data[ptr]) - 1
y1 = int(data[ptr + 1]) - 1
y2 = int(data[ptr + 2]) - 1
ch = data[ptr + 3]
ptr += 4
for r in range(y1, y2 + 1):
graph[r][x] = ch
elif op == "H": # 改變 graph[y][x1] ~ graph[y][x2] 為指定的顏色
x1 = int(data[ptr]) - 1
x2 = int(data[ptr + 1]) - 1
y = int(data[ptr + 2]) - 1
ch = data[ptr + 3]
ptr += 4
graph[y][x1 : x2 + 1] = [ch] * (x2 - x1 + 1)
elif op == "K": # 改變 graph[y1][x1] ~ graph[y2][x2] 的矩形區域為指定的顏色
x1 = int(data[ptr]) - 1
y1 = int(data[ptr + 1]) - 1
x2 = int(data[ptr + 2]) - 1
y2 = int(data[ptr + 3]) - 1
ch = data[ptr + 4]
ptr += 5
for r in range(y1, y2 + 1):
for c in range(x1, x2 + 1):
graph[r][c] = ch
elif op == "F": # 將 graph[y][x] 及相鄰同色的格子改為指定的顏色
x = int(data[ptr]) - 1
y = int(data[ptr + 1]) - 1
ch = data[ptr + 2]
ptr += 3
target = graph[y][x] # 目標顏色
if target == ch: continue # 目標顏色與新的顏色相同，不需要改變
graph[y][x] = ch
que = deque([(y, x)])
while que: # BFS
r, c = que.popleft()
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and graph[nr][nc] == target:
graph[nr][nc] = ch
que.append((nr, nc))
elif op == "S": # 儲存圖片，印出檔名及目前的圖片
name = data[ptr]
result.append(f"{name}\n")
for row in graph[:n]: # 只印出 graph[0][0] ~ graph[n-1][m-1]
res = "".join(map(str, row[:m])) + "\n"
result.append(res)
elif op == "X": # 結束操作
continue
# 輸出答案
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
C++ 程式碼
使用時間約為 5 ms，記憶體約為 3.6 MB，通過測試。
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
vector<string> graph; // 圖片
int m = 0, n = 0; // 圖片尺寸 n 列 m 欄
string op;
while(cin >> op) {
if (op == "I") { // 建立 n 列 m 欄的圖片，內容皆為 O
cin >> m >> n;
string row (m, 'O');
graph.assign(n, row);
} else if (op == "C") { // 重置 n 列 m 欄的圖片，內容皆為 O
string row (m, 'O');
graph.assign(n, row);
} else if (op == "L") { // 改變 graph[y][x] 為指定的顏色
int x, y;
char ch;
cin >> x >> y >> ch;
graph[y - 1][x - 1] = ch;
} else if (op == "V") { // 改變 graph[y1][x] ~ graph[y2][x] 為指定的顏色
int x, y1, y2;
char ch;
cin >> x >> y1 >> y2 >> ch;
x--; y1--; y2--;
for(int r = y1; r <= y2; r++) {
graph[r][x] = ch;
}
} else if (op == "H") { // 改變 graph[y][x1] ~ graph[y][x2] 為指定的顏色
int x1, x2, y;
char ch;
cin >> x1 >> x2 >> y >> ch;
x1--; x2--; y--;
for(int c = x1; c <= x2; c++) {
graph[y][c] = ch;
}
} else if (op == "K") { // 改變 graph[y1][x1] ~ graph[y2][x2] 的矩形區域為指定的顏色
int x1, x2, y1, y2;
char ch;
cin >> x1 >> y1 >> x2 >> y2 >> ch;
x1--; y1--; x2--; y2--;
for(int r = y1; r <= y2; r++) {
for(int c = x1; c <= x2; c++) {
graph[r][c] = ch;
}
}
} else if (op == "F") { // 將 graph[y][x] 及相鄰同色的格子改為指定的顏色
int x, y;
char ch;
cin >> x >> y >> ch;
x--; y--;
char target = graph[y][x]; // 目標顏色
if (target == ch) continue; // 目標顏色與新的顏色相同，不需要改變
graph[y][x] = ch;
queue<pair<int, int>> que;
que.push({y, x});
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
while(!que.empty()) { // BFS
int r = que.front().first, c = que.front().second;
que.pop();
for(int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && graph[nr][nc] == target) {
graph[nr][nc] = ch;
que.push({nr, nc});
}
}
}
} else if (op == "S") { // 儲存圖片，印出檔名及目前的圖片
string name;
cin >> name;
cout << name << "\n";
for(auto row : graph) {
cout << row << "\n";
}
} else if (op == "X") { // 結束操作
continue;
}
}
return 0;
}
C 語言程式碼
使用時間約為 5 ms，記憶體約為 2.2 MB，通過測試。
#include <stdio.h>
typedef struct {
int r, c;
} Pos;
int main() {
char graph[250][250]; // 圖片，題目上限 250 * 250
int m = 0, n = 0; // 圖片尺寸 n 列 m 欄
char op;
while(scanf(" %c", &op) != EOF) {
if (op == 'I') { // 建立 n 列 m 欄的圖片，內容皆為 O
scanf("%d %d", &m, &n);
for(int r = 0; r < n; r++) {
for(int c = 0; c < m; c++) {
graph[r][c] = 'O';
}
}
} else if (op == 'C') { // 重置 n 列 m 欄的圖片，內容皆為 O
for(int r = 0; r < n; r++) {
for(int c = 0; c < m; c++) {
graph[r][c] = 'O';
}
}
} else if (op == 'L') { // 改變 graph[y][x] 為指定的顏色
int x, y;
char ch;
scanf("%d %d %c", &x, &y, &ch);
graph[y - 1][x - 1] = ch;
} else if (op == 'V') { // 改變 graph[y1][x] ~ graph[y2][x] 為指定的顏色
int x, y1, y2;
char ch;
scanf("%d %d %d %c", &x, &y1, &y2, &ch);
x--; y1--; y2--;
for(int r = y1; r <= y2; r++) {
graph[r][x] = ch;
}
} else if (op == 'H') { // 改變 graph[y][x1] ~ graph[y][x2] 為指定的顏色
int x1, x2, y;
char ch;
scanf("%d %d %d %c", &x1, &x2, &y, &ch);
x1--; x2--; y--;
for(int c = x1; c <= x2; c++) {
graph[y][c] = ch;
}
} else if (op == 'K') { // 改變 graph[y1][x1] ~ graph[y2][x2] 的矩形區域為指定的顏色
int x1, x2, y1, y2;
char ch;
scanf("%d %d %d %d %c", &x1, &y1, &x2, &y2, &ch);
x1--; y1--; x2--; y2--;
for(int r = y1; r <= y2; r++) {
for(int c = x1; c <= x2; c++) {
graph[r][c] = ch;
}
}
} else if (op == 'F') { // 將 graph[y][x] 及相鄰同色的格子改為指定的顏色
int x, y;
char ch;
scanf("%d %d %c", &x, &y, &ch);
x--; y--;
char target = graph[y][x]; // 目標顏色
if (target == ch) continue; // 目標顏色與新的顏色相同，不需要改變
graph[y][x] = ch;
Pos que[90000]; // 最多走 250 * 250 = 87500 格
que[0].c = x; que[0].r = y;
int head = 0, total = 1; // 讀取 que 的索引值，que 的總長
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 位移量
while(head < total) { // BFS
int r = que[head].r, c = que[head].c;
head++;
for(int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && graph[nr][nc] == target) {
graph[nr][nc] = ch;
que[total].r = nr;
que[total].c = nc;
total++;
}
}
}
} else if (op == 'S') { // 儲存圖片，印出檔名及目前的圖片
char name[250];
scanf(" %s", name);
printf("%s\n", name);
for(int r = 0; r < n; r++) {
for(int c = 0; c < m; c++) {
printf("%c", graph[r][c]);
}
printf("\n");
}
} else if (op == 'X') { // 結束操作
continue;
}
}
return 0;
}
沒有留言:
張貼留言