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

Use BFS to paint the canvas. The termination conditions include when there is no starting point and when the number of BFS runs is greater than or equal to T, which represents the Manhattan distance, i.e., the number of steps BFS has taken.

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