i177 - 小畫家 (Painter)
題目描述
題目描述了在一個二維點陣圖上，使用「填入色彩」功能，將與指定像素相鄰且顏色相同的像素區域填充為指定顏色。要求輸出填充顏色後的點陣圖。
解題思路
本題可以使用廣度優先搜尋 (BFS) 或深度優先搜尋 (DFS) 來解決。程式碼採用了 BFS 的方法。首先，讀取點陣圖的尺寸、起始像素座標和目標顏色。然後，使用 BFS 從起始像素開始，遍歷所有與起始像素顏色相同且相鄰的像素。在遍歷過程中，將這些像素的顏色更改為目標顏色。最後，輸出修改後的點陣圖。使用 vst 陣列記錄已訪問的像素，避免重複訪問。
複雜度分析
- 時間複雜度: O(H * W)，其中 H 是點陣圖的高度，W 是點陣圖的寬度。因為最壞情況下，BFS 需要遍歷整個點陣圖。
- 空間複雜度: O(H * W)，在最壞的情況下，所有像素都屬於同一個連通域，
q佇列和vst陣列都需要儲存所有像素的信息。
程式碼
#include <iostream>
#include <queue>
using namespace std;
int n,m,x,y,z,a[505][505],v;
bool vst[505][505];
queue <pair <int,int>> q;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> m >> x >> y >> z;
--x;
--y;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
cin >> a[i][j];
v=a[x][y];
q.push({x,y});
while(!q.empty()){
int tx=q.front().first,ty=q.front().second;
q.pop();
if(tx<0||ty<0||tx>=n||ty>=m||vst[tx][ty]||a[tx][ty]!=v)continue;
vst[tx][ty]=1;
q.push({tx-1,ty});
q.push({tx+1,ty});
q.push({tx,ty-1});
q.push({tx,ty+1});
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(vst[i][j]){
cout << z << " ";
}
else{
cout << a[i][j] << " ";
}
}
cout << "\n";
}
}