ZeroJudge D626: 小畫家真好用

Windows的小畫家真好用！
(至少在處理 PrintScreen 方面蠻快的…)
大家都知道
小畫家裡面有一種繪圖工具
叫做油漆桶工具
只要選定你要的顏色、油漆的地點就可以進行填色
油漆桶的填色範圍是取決於”同色塊相鄰”的原則
現在請你模擬這項工具

範例測資

範例輸入範例輸出
每個測資點只有一筆測資。
第一行有整數 N (1 <= N <= 100)表示這張圖的大小是 (N *N) 個字元
接下來的 N 行，每行 N 個字元表示這張圖的樣子。
只有「+」和「-」兩種字元組成 (兩種顏色的意思)
在最後一行，有兩個整數 i, j 表示油漆桶點擊的地點是第 (i + 1) 列第 (j + 1) 個字元。
假設有圖如下 3 * 3：
  012
0：—
1：-+-
2：-++
那麼 0, 2 就表示這格：
 012
0–*
1-+-
2-++
請視選取的顏色為「+」，選取的位置原本的顏色必為「-」。
並且墨水只會利用上下左右四個方位擴散。		請直接輸出經過油漆桶塗色後的圖案。
7
-+++—
-+–+–
-+—+-
–+++–
—++–
3 4
-+++—
-++++–
-+++++-
–+++–
—++–

解題思路

使用 BFS，並且要紀錄每一次走過的點，只要走過就不能再走，不能會造成無窮迴圈。另外，每走到一個點就要將目前位置的字元改成「+」。

範例程式碼－ZeroJudge D626: 小畫家真好用

#include <iostream>
#include <vector>
using namespace std;

int N, walk[200][200] = {}, loc[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char draw[200][200] = {};

void BFS(const vector<pair<int, int>>start) {
    if (start.size() == 0) return;
    vector<pair<int, int>>newStart;
    for (int i = 0; i<start.size(); i++) {
        const int y = start[i].first, x = start[i].second;
        walk[y][x]++;
        draw[y][x] = '+';
        for (int j = 0; j<4; j++) {
            const int yy = y + loc[j][0], xx = x + loc[j][1];
            if (yy >= 0 && yy < N && xx >= 0 && xx < N && draw[yy][xx] == '-' && walk[yy][xx] == 0) {
                newStart.push_back(make_pair(yy, xx));
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i<N; i++) {
        for (int j = 0; j<N; j++) {
            cin >> draw[i][j];
            walk[i][j] = 0;
        }
    }
    vector<pair<int, int>>start;
    int x, y;
    cin >> x >> y;
    start.push_back(make_pair(x, y));
    BFS(start);
    for (int i = 0; i<N; i++) {
        for (int j = 0; j<N; j++) {
            cout << draw[i][j];
        }
        cout << "\n";
    }
}

//ZeroJudge D626
//Dr. SeanXD
標籤

相關文章

發佈留言