Editorial for 動線安排 (APCS 2021-11 中級)


簡潔題意

\(m \times n\) 的展場,\(h\) 次操作。r c 0=在 \((r, c)\) 放木樁:先拆掉經過該格的線,再分別往上、下、左、右找最近的木樁,找得到就把兩根木樁之間的格子連成線;r c 1=拆掉 \((r, c)\) 的木樁,它往四個方向連出去的線一起拆,兩側的木樁不會自動重接。水平線與垂直線可以在同一格交叉、拆其中一種另一種要留著;有木樁或至少一種線的格子就算占用一格。輸出過程中曾出現的最大占用格數,以及最後的占用格數(\(1 \le m, n \le 100\)、\(1 \le h \le 200\))。

依正確通過的測試資料筆數給分,其中:

  • 子題組 1(\(50\) 分):\(m = 1\)。
  • 子題組 2(\(50\) 分):無額外限制。

先拿下子題組 1(50 分):只有一列,線只會是水平的

\(m = 1\) 時展場是一條線,只有「往左」「往右」兩個方向,線也只有水平一種。每一格記兩件事就夠:wood[c](有沒有木樁)和 has_line[c](有沒有線經過),兩個 bool 陣列(上冊 6.5= {} 全部設成 false)。

兩種操作其實是同一件事的正反面:放木樁=往左、往右各找最近的木樁,把中間的格子畫上線;拆木樁=一樣往左、往右找最近的木樁,把中間的格子擦掉。「找最近的木樁」就是從隔壁那一格開始、一格一格走到撞到木樁或出界為止(上冊 4.2while);畫線和擦線只差寫進去的是 true 還是 false,所以直接寫 has_line[x] = (t == 0)(上冊 3.1:把比較的結果存進 bool)。

#include <iostream>
using namespace std;

const int MAX_N = 100;

int main() {
    int m, n, h;
    cin >> m >> n >> h;                    // 子題組 1 保證 m = 1:展場只有一列
    bool wood[MAX_N] = {};                 // 這格有沒有木樁
    bool has_line[MAX_N] = {};             // 這格有沒有線經過(只有一列,線只會是水平的)

    int best = 0;                          // 過程中最大的占用格數
    int cnt = 0;                           // 目前的占用格數
    for (int op = 0; op < h; op++) {
        int r, c, t;
        cin >> r >> c >> t;                // r 一定是 0,照格式讀掉就好

        // 往左找最近的木樁:從隔壁那格開始走,走到撞到木樁或出界為止
        int left = c - 1;
        while (left >= 0 && !wood[left]) {
            left--;
        }
        if (left >= 0) {                   // 沒出界=找到了:中間的格子放木樁就畫線、拆木樁就擦線
            for (int x = left + 1; x < c; x++) {
                has_line[x] = (t == 0);
            }
        }

        // 往右找最近的木樁,同樣處理
        int right = c + 1;
        while (right < n && !wood[right]) {
            right++;
        }
        if (right < n) {
            for (int x = c + 1; x < right; x++) {
                has_line[x] = (t == 0);
            }
        }

        // 最後處理自己這一格
        if (t == 0) {
            wood[c] = true;
            has_line[c] = false;           // 木樁那一格不算線
        } else {
            wood[c] = false;
        }

        // 數一數目前占用幾格,順便更新最大值
        cnt = 0;
        for (int j = 0; j < n; j++) {
            if (wood[j] || has_line[j]) {
                cnt++;
            }
        }
        if (cnt > best) {
            best = cnt;
        }
    }
    cout << best << '\n';
    cout << cnt << '\n';
    return 0;
}

三個地方別踩:

  • 找最近木樁要從隔壁那格開始走——從自己這格開始,拆木樁時會立刻找到自己。
  • 放木樁那一格要把線清掉:題目說「先拆掉經過該格的線」,這一格從此是木樁、不是線。經過它的那條線兩端的木樁,正好就是接下來左右找到的「最近木樁」,線會被重新畫回來——所以除了清掉這一格,什麼都不用特別做。
  • 最大值每做完一次操作就要看一次,不是最後才看。

⚠️ 兩個範例都是 \(m > 1\) 的展場,這份程式兩個範例都會 WA——要自己造 \(m = 1\) 的小測資驗(下面自測表的前三列就是),逐筆給分之下子題組 1 的 \(50\) 分穩穩到手。

從 50 分到 100 分:兩個方向變四個,線的表變兩張

二維之後多了兩件事:方向從左右兩個變成上下左右四個——打成方向表 dr[]dc[]13.3),「找最近木樁」一樣是沿方向一直走(13.5 的射線);線分成垂直、水平兩種、同一格可以交叉、拆一種要留另一種——所以線的表要開兩張line_v[r][c]line_h[r][c]vector<vector<bool>>10.3)。往上下方向畫的是垂直線、往左右畫的是水平線,用 dr[dir] 是不是 \(0\) 就分得出來。

子題版「往左一段、往右一段」幾乎一樣的程式碼,到了四個方向就會變成四段——所以把它們包成函式:find_nearest 沿方向找最近木樁,找到就把位置透過參考參數帶回來(上冊 7.5);set_line 依方向決定寫進哪一張線表;oper 把四個方向跑一遍。占用格數=有木樁、或兩種線至少一種。

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

const int INSERT_OPER = 0;   // 操作 0:放木樁
const int REMOVE_OPER = 1;   // 操作 1:拆木樁

// 四個方向:下、右、上、左——dr[dir]、dc[dir] 是往該方向走一步時列、行各加多少
const int dr[4] = {1, 0, -1, 0};
const int dc[4] = {0, 1, 0, -1};

int m, n;
vector<vector<bool>> wood;     // 這格有沒有木樁
vector<vector<bool>> line_v;   // 這格有沒有垂直線經過
vector<vector<bool>> line_h;   // 這格有沒有水平線經過

bool valid(int r, int c) {
    return r >= 0 && r < m && c >= 0 && c < n;
}

// 從 (r, c) 往方向 dir 找最近的木樁:找到就把位置放進 (nr, nc) 並回傳 true,走到出界就回傳 false
bool find_nearest(int r, int c, int dir, int &nr, int &nc) {
    r += dr[dir];
    c += dc[dir];
    while (valid(r, c) && !wood[r][c]) {
        r += dr[dir];
        c += dc[dir];
    }
    if (valid(r, c)) {
        nr = r;
        nc = c;
        return true;
    }
    return false;
}

// 把 (r, c) 這格「方向 dir 的那種線」設成 value:上下方向畫的是垂直線、左右方向畫的是水平線
void set_line(int r, int c, int dir, bool value) {
    if (dr[dir] != 0) {
        line_v[r][c] = value;
    } else {
        line_h[r][c] = value;
    }
}

// 在 (r, c) 做一次操作:放木樁就往四個方向連線、拆木樁就把那四段線擦掉
void oper(int r, int c, int t) {
    for (int dir = 0; dir < 4; dir++) {
        int nr, nc;
        if (find_nearest(r, c, dir, nr, nc)) {
            // (r, c) 與 (nr, nc) 之間、不含兩端的每一格:放木樁=畫線(true)、拆木樁=擦線(false)
            for (int x = r + dr[dir], y = c + dc[dir]; x != nr || y != nc; x += dr[dir], y += dc[dir]) {
                set_line(x, y, dir, t == INSERT_OPER);
            }
        }
    }
    if (t == INSERT_OPER) {
        wood[r][c] = true;
        line_v[r][c] = false;   // 木樁那一格不算線:原本經過的線在這裡被拆掉
        line_h[r][c] = false;
    } else {
        wood[r][c] = false;
    }
}

// 目前占用的格子數:有木樁、或至少一個方向有線
int count_not_empty() {
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (wood[i][j] || line_v[i][j] || line_h[i][j]) {
                cnt++;
            }
        }
    }
    return cnt;
}

int main() {
    int h;
    cin >> m >> n >> h;
    wood.assign(m, vector<bool>(n, false));
    line_v.assign(m, vector<bool>(n, false));
    line_h.assign(m, vector<bool>(n, false));

    int best = 0;
    while (h--) {
        int r, c, t;
        cin >> r >> c >> t;
        oper(r, c, t);
        best = max(best, count_not_empty());   // 每一次操作後都要看一次
    }
    cout << best << '\n' << count_not_empty() << '\n';
    return 0;
}

跟子題版比,換掉的東西:

  • 左右兩個方向變四個left--right++ 換成 dr[dir]dc[dir],「找最近木樁」寫成 find_nearest 一個函式、帶回一組座標 (nr, nc)
  • 一張線的表變兩張set_line 依方向決定寫進 line_v 還是 line_h;拆垂直線時水平線原封不動,交叉格因此還算占用。
  • 每一次操作的骨架完全一樣:四個方向各找一次最近木樁、中間畫線或擦線,最後處理自己這一格——只是收進 oper 裡。

拆木樁時「往四個方向找最近的木樁、把中間擦掉」為什麼擦得對?線只會畫在相鄰兩根木樁之間(畫的時候找的就是最近的),所以某個方向最近的木樁若跟自己有線相連,中間那段就是要擦的;沒有相連(例如中間曾經有一根木樁被拆掉、兩邊沒重接),中間本來就沒有這一種線,擦了也不影響別的東西——交叉的另一種線在另一張表裡。

會不會太慢?每次操作往四個方向各走最多 \(100\) 格、再數一遍 \(100 \times 100\) 的表,\(200\) 次操作總共兩百萬次左右,離一秒遠得很。

測過再交:範例沒有 \(m = 1\),也沒有「拆完不重接」的最小情況

兩個範例都是二維的、也都有交叉與拆線,該考的幾乎都考了——但都要對著圖數十幾格才驗得了,錯了也看不出是哪一段錯。用手算得動的最小測資自己造,前三列同時是子題組 1 的驗收:

輸入 正確輸出 這一筆在測什麼
1 3 20 0 00 2 0 33 最小的一列:兩根木樁夾一格線
1 5 40 0 00 4 00 2 00 2 1 52 拆掉中間的木樁:兩側不重接,只剩兩根木樁——重接的程式會印 55
1 5 30 0 00 4 00 2 0 55 把木樁放到有線經過的格子:先拆線、再往左右重新接回來,占用格數不變
3 3 51 0 01 2 00 1 02 1 00 1 1 54 中央 \((1, 1)\) 是十字交叉:只算一格;拆掉上面的木樁後垂直線沒了、水平線還在——只有一張線表的程式會印 53

四筆都親眼看過正確,這題就穩了。

常犯錯誤
  • 拆木樁後把兩側的木樁重新接起來:題目明寫不會自動重接。範例 1 印 109(該印 106)、範例 2 印 1210
  • 只開一張線的表、不分垂直水平:拆一個方向的線時把交叉的另一條也擦掉了——範例 2 最後印 6(該印 7),最大值 12 照樣對。
  • 放木樁時沒把那一格的線清掉:木樁還在時看不出來(有木樁就算占用),拆掉之後那格殘留一條假的線——範例 2 最後印 8(該印 7)。
  • find_nearest 從自己這一格開始找:拆木樁時最近的木樁就是自己,擦線的迴圈停不下來、一路走出展場,兩個範例都直接當掉。
  • 最大值只在最後算:範例 1 印 66、範例 2 印 77
  • 交叉格算兩次(木樁、垂直線、水平線分開加):範例 2 最大值印 13(該印 12)。