你是一個遊樂園展場的管理員，展場是一個 M×N 的矩形，可以使用木樁和線來排動線，你可以有兩種操作：
- 加入木樁 r c 0
加一木樁在 (r, c)，並且向他的上下左右盡量找離最近的木樁連線，題目保證 (r, c) 上一定沒有木樁，若 (r, c) 有線經過則先將那些線拆掉後再來連線。 - 移除木樁 r c 1
(r, c) 拔木樁，並把他的線也拔掉，保證 (r, c) 上一定有木樁。
總共有 h 次操作，輸出過程中有線和有木樁佔據空間的面積最大是多少，以及 h 次操作後有線和有木樁佔據空間的面積。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行輸入三個正整數 M、N、H，代表展場範圍是 M×N 並且有 H 筆操作。 接下來會有 H 行，每一行都有三個非負整數 R、C、T，代表在位置 (R, C) 執行操作 T。 | 輸出兩個數字。 第一個數字表示，操作過程中有線和有木樁佔據空間的面積最大值。 第二個數字表示，操作結束後有線和有木樁佔據空間的面積。 |
| 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: 動線安排
#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