d626 - 小畫家真好用
題目描述
題目要求模擬小畫家中的油漆桶工具。給定一個由 '+' 和 '-' 字符組成的 n x n 網格，以及一個起始點 (x, y)，將起始點的顏色從 '-' 替換為 '+'，並將所有與起始點相鄰且顏色相同的 '-' 字符也替換為 '+'。相鄰定義為上下左右四個方向。
解題思路
這題可以使用深度優先搜尋 (DFS) 來解決。從給定的起始點開始，將該點的顏色更改為 '+'。然後，遞迴地檢查該點的上下左右四個鄰居。如果鄰居的顏色是 '-'，則將其顏色更改為 '+'，並遞迴地對該鄰居執行相同的操作。這個過程會一直持續到沒有更多的 '-' 字符可以更改為 '+'。
複雜度分析
- 時間複雜度: O(n^2)，因為在最壞的情況下，我們可能需要遍歷整個網格。
- 空間複雜度: O(n^2)，因為在最壞的情況下，遞迴調用堆疊的深度可能達到 n^2。
程式碼
#include <iostream>
using namespace std;
char nmap[101][101];
int n,x,y;
void pf(int a,int b){
nmap[a][b]='+';
if(a-1>=0&&nmap[a-1][b]=='-')
pf(a-1,b);
if(a+1<n&&nmap[a+1][b]=='-')
pf(a+1,b);
if(b-1>=0&&nmap[a][b-1]=='-')
pf(a,b-1);
if(b+1<n&&nmap[a][b+1]=='-')
pf(a,b+1);
}
int main(){
cin >> n;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
cin>> nmap[i][j];
cin >> x >> y;
pf(x,y);
for(int i=0;i<n;++i){
for(int j=0;j<n;++j)
cout << nmap[i][j];
cout << "\n";
}
}