ZeroJudge 解題筆記：fl920. P.3 建築倒塌 (Collapse)

作者：王一哲
日期：2025年5月22日



ZeroJudge 題目連結：fl920. P.3 建築倒塌 (Collapse)

解題想法

這題可以用陣列儲存建築物狀態，不斷檢查每棟建築物是否需要更新狀態，直到沒有再更新狀態為止。如果改用集合儲存還要檢查的建築物位置，速度會更快一些。

Python 程式碼

寫法1，不斷檢查每棟建築物是否需要更新狀態，直到沒有再更新狀態為止。使用時間約為 0.3 s，記憶體約為 3.4 MB，通過測試。

import sys

def solve(s):  # 輸入建築物狀態
    n = len(s)  # 建築物數量
    if n <= 1:  # 特例，將 s 組成字串再印出，跳出函式
        print(''.join(s)); return
    cont = True  # 是否需要繼續更新狀態
    while cont:
        t = s[:]  # 暫存建築物狀態
        cont = False  # 先改成 False
        for i in range(n):  # 依序掃過每棟建築物
            if i == 0 and s[i] == 'X' and s[i+1] == 'L':  # 最左側建築物被右側建築物向左壓
                t[i] = 'L'; cont = True
            elif i == n-1 and s[n-1] == 'X' and s[n-2] == 'R':  # 最右側建築物被左側建築物向右壓
                t[n-1] = 'R'; cont = True
            elif 1 <= i <= n-2:  # 中間的建築物
                if s[i-1] == 'R' and s[i+1] == 'L':  # 左側向右倒，右側向左倒，中間不動
                    pass
                elif s[i-1] == 'R' and s[i] == 'X':  # 左側向右倒，中間原來還沒倒
                    t[i] = 'R'; cont = True
                elif s[i+1] == 'L' and s[i] == 'X':  # 右側向左倒，中間原來還沒倒
                    t[i] = 'L'; cont = True
        s = t[:]  # t 的資料存到 s
    print(''.join(s))  # 將 s 組成字串再印出

for arr in sys.stdin:
    arr = list(arr.strip())  # 建築物狀態
    solve(arr)

寫法2，用 set 儲存還要檢查的建築物位置。使用時間約為 0.2 s，記憶體約為 3.4 MB，通過測試。

import sys

def solve(s):  # 輸入建築物狀態
    n = len(s)  # 建築物數量
    if n <= 1:  # 特例，將 s 組成字串再印出，跳出函式
        print(''.join(arr)); return
    rem = set()  # 還要檢查的位置
    m = n  # 還要檢查的位置數量
    for i, c in enumerate(s):  # 依序讀取每棟建築物的狀態
        if c == 'X': rem.add(i)  # 還沒有倒的建築物位置加入 rem
    while rem and m > len(rem):  # 如果 rem 還有資料而且 m 大於 rem 的數量繼續執行
        t = s[:]  # 暫存建築物狀態
        m = len(rem)  # 更新 
        pos = []  # 暫存要從 rem 移除的位置
        for i in rem:  # 讀取還需要更新狀態的建築物位置
            if i == 0 and s[i] == 'X' and s[i+1] == 'L':  # 最左側建築物被右側建築物向左壓
                t[i] = 'L'; pos.append(i)
            elif i == n-1 and s[n-1] == 'X' and s[n-2] == 'R':  # 最右側建築物被左側建築物向右壓
                t[n-1] = 'R'; pos.append(i)
            elif 1 <= i <= n-2:  # 中間的建築物
                if s[i-1] == 'R' and s[i+1] == 'L':  # 左側向右倒，右側向左倒，中間不動
                    pos.append(i)
                elif s[i-1] == 'R' and s[i] == 'X':  # 左側向右倒，中間原來還沒倒
                    t[i] = 'R'; pos.append(i)
                elif s[i+1] == 'L' and s[i] == 'X':  # 右側向左倒，中間原來還沒倒
                    t[i] = 'L'; pos.append(i)
        s = t[:]  # t 的資料存到 s
        for p in pos: rem.remove(p)  # 從 rem 移除 p
    print(''.join(s))  # 將 s 組成字串再印出

for arr in sys.stdin:
    arr = list(arr.strip())  # 建築物狀態
    solve(arr)

C++ 程式碼

使用時間約為 3 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;

void solve(string s) {  // 輸入建築物狀態
    int n = (int)s.size();  // 建築物數量
    if (n <= 1) {  // 特例，印出 s，跳出函式
        cout << s << "\n";
        return;
    }
    bool cont = true;  // 是否需要繼續更新狀態
    while(cont) {
        string t = s;  // 暫存建築物狀態
        cont = false;  // 先改成 False
        for(int i=0; i<n; i++) {  // 依序掃過每棟建築物
            if (i == 0 && s[i] == 'X' && s[i+1] == 'L') {  // 最左側建築物被右側建築物向左壓
                t[i] = 'L'; cont = true;
            } else if (i == n-1 && s[n-1] == 'X' && s[n-2] == 'R') {  // 最右側建築物被左側建築物向右壓
                t[n-1] = 'R'; cont = true;
            } else if (i >= 1 && i <= n-2) {  // 中間的建築物
                if (s[i-1] == 'R' && s[i+1] == 'L') {  // 左側向右倒，右側向左倒，中間不動
                    ;
                } else if (s[i-1] == 'R' && s[i] == 'X') {  // 左側向右倒，中間原來還沒倒
                    t[i] = 'R'; cont = true;
                } else if (s[i+1] == 'L' && s[i] == 'X') {  // 右側向左倒，中間原來還沒倒
                    t[i] = 'L'; cont = true;
                }
            }
        }
        s = t;  // t 的資料存到 s
    }
    cout << s << "\n";  // 印出 s
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string arr;  // 建築物狀態
    while(cin >> arr) solve(arr);
    return 0;
}

使用時間約為 5 ms，記憶體約為 376 kB，通過測試。

#include <iostream>
#include <string>
#include <set>
#include <vector>
using namespace std;

void solve(string s) {  // 輸入建築物狀態
    int n = (int)s.size();  // 建築物數量
    if (n <= 1) {  // 特例，印出 s，跳出函式
        cout << s << "\n";
        return;
    }
    set<int> rem;  // 還要檢查的位置
    int m = n;  // 還要檢查的位置數量
    for(int i=0; i<n; i++) {  // 依序讀取每棟建築物的狀態
        if (s[i] == 'X') rem.insert(i);  // 還沒有倒的建築物位置加入 rem
    }
    while(!rem.empty() && m > (int)rem.size()) {
        string t = s;  // 暫存建築物狀態
        m = (int)rem.size();  // 更新 m
        vector<int> pos;  // 暫存要從 rem 移除的位置
        for(auto i : rem) {  // 讀取還需要更新狀態的建築物位置
            if (i == 0 && s[i] == 'X' && s[i+1] == 'L') {  // 最左側建築物被右側建築物向左壓
                t[i] = 'L'; pos.push_back(i);
            } else if (i == n-1 && s[n-1] == 'X' && s[n-2] == 'R') {  // 最右側建築物被左側建築物向右壓
                t[n-1] = 'R'; pos.push_back(i);
            } else if (i >= 1 && i <= n-2) {  // 中間的建築物
                if (s[i-1] == 'R' && s[i+1] == 'L') {  // 左側向右倒，右側向左倒，中間不動
                    pos.push_back(i);
                } else if (s[i-1] == 'R' && s[i] == 'X') {  // 左側向右倒，中間原來還沒倒
                    t[i] = 'R'; pos.push_back(i);
                } else if (s[i+1] == 'L' && s[i] == 'X') {  // 右側向左倒，中間原來還沒倒
                    t[i] = 'L'; pos.push_back(i);
                }
            }
        }
        s = t;  // t 的資料存到 s
        for(auto p : pos) rem.erase(p);  // 從 rem 移除 p
    }
    cout << s << "\n";  // 印出 s
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string arr;  // 建築物狀態
    while(cin >> arr) solve(arr);
    return 0;
}