ZeroJudge O077: Digital Canvas

There is an H*W digital canvas, where initially all values are 0, indicating no color filled. Next, please simulate N brush operations.

Each brush operation involves selecting a coordinate (R, C) and pausing for T seconds. It will color the blocks within a Manhattan distance <= T with color X. If multiple colors are filled into the same block, the values of the colors will accumulate.

Please output the state of the canvas after N operations.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line inputs three positive integers H, W, and N (1 <= H, W <= 20, 1 <= N <= 100).
Following are N lines, each containing four integers R, C, T, and X (0 <= R <= H, 0 <= C <= W, 0 <= T <= 20, 1 <= X <= 10).		Output the state of the canvas after N brush operations.
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 Sample Test Cases

Thought Process

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

In the parameters of BFS, you need a map to keep track of which points have been visited. Let's call this map "all." If all[current_coordinate] == 0, then X can be added to the current coordinate. Also, every time you move to any coordinate, you need to increment all[coordinate]++. This is because in the same Nth BFS run, the same point can only be added with X once, and it cannot be accumulated.

Additionally, to avoid timeouts, you can declare a map to keep track of the starting points for the next BFS run. Let's call this map "add." When adding a new starting point for the next BFS run, increment add[coordinate]++, and when adding a new point, check if add[coordinate] is 0. If it's 0, then add this coordinate as a starting point.

Sample Code－ZeroJudge O077: Digital Canvas

#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
Tags

Related Posts

Comments