ZeroJudge G596: Route Arrangement

You are the manager of an amusement park exhibition. The exhibition space is an M×N rectangle, and you can use stakes and lines to organize the queue. You have two types of operations:

  • Add a stake at (r, c) 0:
    Place a stake at (r, c) and try to connect it with the nearest stakes above, below, left, and right. The problem guarantees that there is no stake at (r, c). If there are any lines passing through (r, c), those lines must be removed before making the connections.
  • Remove a stake at (r, c) 1:
    Pull out the stake at (r, c) and remove its lines as well. The problem guarantees that there is a stake at (r, c).

You will perform a total of h operations. You need to output the maximum area occupied by lines and stakes during the process, as well as the area occupied by lines and stakes after all h operations.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains three positive integers M, N, and H, representing the exhibition area as M \times N and H operations. Following this, there are H lines, each containing three non-negative integers R, C, and T, indicating the operation T to be performed at position (R, C).Output two numbers.
The first number indicates the maximum area occupied by lines and stakes during the operations.
The second number indicates the area occupied by lines and stakes after all operations are completed.
3 5 6
0 0 0
0 2 0
2 2 0
2 0 0
2 4 0
2 2 1		10
6
5 5 7
2 2 0
2 4 0
4 4 0
4 0 0
0 3 0
4 3 0
4 3 1		12
7
ZeroJudge G596 Sample Test Cases

Thought Process

When inserting a stake, check for the nearest stakes in the up, down, left, and right directions, and connect lines accordingly.

When removing a stake, check for the nearest stakes in the up, down, left, and right directions to determine whether to connect or remove lines. If there are no stakes at both ends in the same direction (vertical or horizontal), you should remove the line; otherwise, you should connect it. It's important to determine whether you are dealing with vertical or horizontal lines during this process.

Sample Code－ZeroJudge G596: Route Arrangement

#include <iostream>
using namespace std;

char verticalLine(const char ch) {
    if (ch == '.' || ch == 'V') {
        return 'V';
    }
    return 'B';
}

char horizontalLine(const char ch) {
    if (ch == '.' || ch == 'H') {
        return 'H';
    }
    return 'B';
}

char deleteVerticalLine(const char ch) {
    if (ch == 'B') return 'H';
    return '.';
}

char deleteHorizontalLine(const char ch) {
    if (ch == 'B') return 'V';
    return '.';
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M, H, max = -999, final = 0;
    cin >> N >> M >> H;
    char arcade[100][100] = {};
    for (int i = 0; i<N; i++) {
        for (int j = 0; j<M; j++) {
            arcade[i][j] = '.';
        }
    }
    for (int i = 0; i<H; i++) {
        int R, C, T;
        cin >> R >> C >> T;
        if (T == 0) {
            arcade[R][C] = 'W';
            for (int j = R-1; j>=0; j--) {
                if (arcade[j][C] == 'W') {
                    for (int k = j+1; k<R; k++) {
                        arcade[k][C] = verticalLine(arcade[k][C]);
                    }
                    break;
                }
            }
            for (int j = R+1; j<N; j++) {
                if (arcade[j][C] == 'W') {
                    for (int k = j-1; k>R; k--) {
                        arcade[k][C] = verticalLine(arcade[k][C]);
                    }
                    break;
                }
            }
            for (int j = C-1; j>=0; j--) {
                if (arcade[R][j] == 'W') {
                    for (int k = j+1; k<C; k++) {
                        arcade[R][k] = horizontalLine(arcade[R][k]);
                    }
                    break;
                }
            }
            for (int j = C+1; j<M; j++) {
                if (arcade[R][j] == 'W') {
                    for (int k = j-1; k>C; k--) {
                        arcade[R][k] = horizontalLine(arcade[R][k]);
                    }
                    break;
                }
            }
        }
        else {
            arcade[R][C] = '.';
            for (int j = R-1; j>=0; j--) {
                if (arcade[j][C] == 'W') {
                    for (int k = j+1; k<R; k++) {
                        arcade[k][C] = deleteVerticalLine(arcade[k][C]);
                    }
                    break;
                }
            }
            for (int j = R+1; j<N; j++) {
                if (arcade[j][C] == 'W') {
                    for (int k = j-1; k>R; k--) {
                        arcade[k][C] = deleteVerticalLine(arcade[k][C]);
                    }
                    break;
                }
            }
            for (int j = C-1; j>=0; j--) {
                if (arcade[R][j] == 'W') {
                    for (int k = j+1; k<C; k++) {
                        arcade[R][k] = deleteHorizontalLine(arcade[R][k]);
                    }
                    break;
                }
            }
            for (int j = C+1; j<M; j++) {
                if (arcade[R][j] == 'W') {
                    for (int k = j-1; k>C; k--) {
                        arcade[R][k] = deleteHorizontalLine(arcade[R][k]);
                    }
                    break;
                }
            }
        }
        int count = 0;
        for (int j = 0; j<N; j++) {
            for (int k = 0; k<M; k++) {
                if (arcade[j][k] != '.') count++;
            }
        }
        if (count > max) max = count;
        if (i == H-1) final = count;
    }
    cout << max << "\n" << final << "\n";
}

//ZeroJudge G596
//Dr. SeanXD
Tags

Related Posts

Comments