f435 - 10267-Graphical Editor
題目描述
題目描述一個圖形編輯器，可以進行創建、清除、塗色、畫線、填充等操作。輸入為一系列命令，每行一個命令，命令包含操作類型和參數。最終需要輸出指定名稱的圖片，圖片由字符矩陣表示，每個字符代表一個像素的顏色。
解題思路
這題主要是一個模擬題，需要根據輸入的命令來更新圖形編輯器中的像素顏色。核心操作包括初始化、清除、單點塗色、線段塗色、矩形塗色和區域填充。區域填充使用深度優先搜尋 (DFS) 實現，也稱為 Flood Fill 演算法。
程式碼首先讀取命令，然後根據命令類型執行相應的操作。對於 F 命令，使用 DFS 從給定的座標開始，將與起始像素顏色相同的相鄰像素塗成新的顏色。其他命令則直接更新像素顏色。
複雜度分析
- 時間複雜度: O(M * N * K)，其中 M 和 N 是矩陣的尺寸，K 是命令的數量。最壞情況下，每次
F命令可能需要遍歷整個矩陣。 - 空間複雜度: O(M * N)，主要用於儲存像素顏色矩陣
cv。DFS 的遞迴深度在最壞情況下也可能達到 M * N。
程式碼
#include <iostream>
using namespace std;
char cv[251][251],is,t;
int x,y,z,z2,mx,my;
string name;
void dfs(int x,int y,char c,char g){
if(x<=0||x>mx||y<=0||y>my||cv[y][x]!=c)return;
cv[y][x]=g;
dfs(x+1,y,c,g);
dfs(x-1,y,c,g);
dfs(x,y+1,c,g);
dfs(x,y-1,c,g);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> is){
if(is=='I'){
cin >> x >> y;
mx=x;
my=y;
for(int i=1;i<=my;++i)
for(int j=1;j<=mx;++j)
cv[i][j]='O';
}
else if(is=='C'){
for(int i=1;i<=my;++i)
for(int j=1;j<=mx;++j)
cv[i][j]='O';
}
else if(is=='L'){
cin >> x >> y >> t;
cv[y][x]=t;
}
else if(is=='V'){
cin >> x >> y >> z >> t;
int tmp=min(y,z);
z=max(y,z);
y=tmp;
for(int j=y;j<=z;++j)
cv[j][x]=t;
}
else if(is=='H'){
cin >> x >> z >> y >> t;
int tmp=min(x,z);
z=max(x,z);
x=tmp;
for(int i=x;i<=z;++i)
cv[y][i]=t;
}
else if(is=='K'){
cin >> x >> y >> z >> z2 >> t;
int tmp=min(x,z);
z=max(x,z);
x=tmp;
int tmp2=min(y,z2);
z2=max(y,z2);
y=tmp2;
for(int i=y;i<=z2;++i)
for(int j=x;j<=z;++j)
cv[i][j]=t;
}
else if(is=='F'){
cin >> x >> y >> t;
if(cv[y][x]!=t)dfs(x,y,cv[y][x],t);
}
else if(is=='S'){
cin >> name;
cout << name << "\n";
for(int i=1;i<=my;++i){
for(int j=1;j<=mx;++j)
cout << cv[i][j] ;
cout << "\n";
}
}
else if(is=='X')break;
else
getline(cin,name);
}
}