d537 - 4. 染色遊戲
題目描述
題目描述了一個在 NxN 的白布上染色擴散的過程。給定紅、黃、藍三種顏色的墨水滴落位置，以及一個目標顏色，要求計算目標顏色在白布上曾出現的最大面積。擴散以正方形方式進行，顏色混合遵循特定規則（黃+藍=綠，黃+紅=橘，三色混合=黑）。
解題思路
程式碼使用模擬的方式來計算顏色擴散和混合。它使用三個二維陣列 r、b 和 yl 分別記錄紅色、藍色和黃色墨水的擴散範圍。對於每個擴散時間 t，程式會將三種顏色的墨水擴散到 (x, y) 周圍的 2t+1 x 2t+1 的正方形區域。然後，程式遍歷整個白布，檢查每個格子是否被三種顏色染色，並計算目標顏色出現的面積。程式會記錄並更新最大面積。
複雜度分析
- 時間複雜度: O(n^3)
- 空間複雜度: O(n^2)
程式碼
#include <iostream>
#include <map>
using namespace std;
int r[105][105],b[105][105],yl[105][105],a[3][2],x,y,n,ans;
char c;
map <char,int> mp;
void rd(int x,int y,int t){
for(int i=-t;i<=t;++i){
for(int j=-t;j<=t;++j){
if(x+i<=n&&y+j<=n&&x+i>0&&y+j>0){
r[x+i][y+j]=1;
}
}
}
}
void bd(int x,int y,int t){
for(int i=-t;i<=t;++i){
for(int j=-t;j<=t;++j){
if(x+i<=n&&y+j<=n&&x+i>0&&y+j>0){
b[x+i][y+j]=2;
}
}
}
}
void yd(int x,int y,int t){
for(int i=-t;i<=t;++i){
for(int j=-t;j<=t;++j){
if(x+i<=n&&y+j<=n&&x+i>0&&y+j>0){
yl[x+i][y+j]=4;
}
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
mp['R']=1;
mp['B']=2;
mp['Y']=4;
mp['O']=5;
mp['P']=3;
mp['G']=6;
mp['D']=7;
cin >> n;
for(int i=0;i<3;++i){
cin >> c >> x >> y;
++x;
++y;
if(c=='R'){
a[0][0]=x;
a[0][1]=y;
}
if(c=='B'){
a[1][0]=x;
a[1][1]=y;
}
if(c=='Y'){
a[2][0]=x;
a[2][1]=y;
}
}
cin >> c;
for(int i=0;i<=n;++i){
rd(a[0][0],a[0][1],i);
bd(a[1][0],a[1][1],i);
yd(a[2][0],a[2][1],i);
int tmp=0;
for(int ii=1;ii<=n;++ii){
for(int jj=1;jj<=n;++jj){
if(r[ii][jj]+b[ii][jj]+yl[ii][jj]==mp[c]){
++tmp;
}
}
}
ans=max(tmp,ans);
}
cout << ans;
}