ZeroJudge O077: 電子畫布

有一個 H＊W 的電子畫布，一開始數值都是 0 代表未填色，接下來請模擬 N 次畫筆操作。

每次畫筆操作為選一個座標 (R, C) 停留 T 秒，他會將曼哈頓距離 <= T 的區塊染上顏色 X。若有多個顏色重複填到相同區塊，顏色的數值會累加起來。

請輸出 N 次操作後的畫布狀態。

範例測資

範例輸入範例輸出
第一行輸入三個正整數 H、W、N (1 <= H、W <= 20，1 <= N <= 100)。
接下來有 N 行，每一行有四個整數 R、C、T、X (0 <= R <= H，0 <= C <= W，0 <= t <= 20，1 <= X <= 10)。		輸出畫布做 N 次畫筆操作後的狀態。
1 20 3
0 13 5 7
0 6 4 4
0 13 12 6		0 6 10 10 10 10 10 10 17 17 17 13 13 13 13 13 13 13 13 6
6 7 3
3 2 2 1
1 6 1 2
1 3 2 5		0 0 5 5 5 0 2
0 5 6 5 5 7 2
0 1 6 6 5 0 2
1 1 1 6 1 0 0
0 1 1 1 0 0 0
0 0 1 0 0 0 0
ZeroJudge O077 範例測資

解題思路

使用 BFS 的方式來畫畫，終止條件除了當沒有起點時，當跑 BFS 的次數 >= T 時也要終止，曼哈頓距離其實就是走了幾步的意思，也就是 BFS 跑的次數。

在 BFS 的參數中需要有一個 map 來存取已經走過哪些點了，這邊取名叫做 all，如果 all[現在座標] == 0 才能給目前座標加上 X，並且每次走到任何座標都需要 all[座標]++，因為在同樣的第 N 次 BFS 中，同一個點只能被加一次 X，不能累加。

另外，為了避免超時，可以宣告一個 map 來存取下一次 BFS 已經有的起點，這邊取名叫做 add。當新增了下一次 BFS 的起點時，add[座標]++，並且要新增時需要判斷 add[座標] 是否為 0，如果是 0 才要新增這個座標。

範例程式碼－ZeroJudge O077: 電子畫布

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

int H, W, N, num[30][30] = {}, loc[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int R, C, T, X;

pair<int, int> axis (const int a, const int b) {
    pair<int, int>tmp;
    tmp.first = a;
    tmp.second = b;
    return tmp;
}

void BFS(vector<pair<int, int>>start, map<pair<int, int>, int>MAP, const int time, map<pair<int, int>, int>all) {
    if (time == T+1) return;
    if (start.empty()) return;
    vector<pair<int, int>>newStart;
    map<pair<int, int>, int>add;
    for (int i = 0; i<start.size(); i++) {
        MAP[start[i]]++;
        const int y = start[i].first, x = start[i].second;
        if (all[start[i]] == 0) num[y][x] += X;
        all[start[i]]++;
        for (int j = 0; j<4; j++) {
            const int yy = y + loc[j][0], xx = x + loc[j][1];
            if (yy >= 0 && yy < H && xx >= 0 && x < W && MAP[axis(yy, xx)] == 0 && add[axis(yy, xx)] == 0) {
                newStart.push_back(axis(yy, xx));
                add[axis(yy, xx)]++;
            }
        }
    }
    BFS(newStart, MAP, time+1, all);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> H >> W >> N;
    for (int i = 0; i<H; i++) {
        for (int j = 0; j<W; j++) num[i][j] = 0;
    }
    for (int i = 0; i<N; i++) {
        cin >> R >> C >> T >> X;
        vector<pair<int, int>>start;
        start.push_back(axis(R, C));
        map<pair<int, int>, int>MAP;
        BFS(start, MAP, 0, MAP);
    }
    for (int i = 0; i<H; i++) {
        for (int j = 0; j<W; j++) cout << num[i][j] << " ";
        cout << "\n";
    }
}

//ZeroJudge O077
//Dr. SeanXD
標籤

相關文章

發佈留言