CodeForces 545A：矩陣碰撞判斷完好車輛

題目大意

給定 n×n 矩陣，對角線為 -1（自身不碰撞）。0 表示無碰撞，1 表示第 i 輛車（行）被撞壞，2 表示第 j 輛車（列）被撞壞，3 表示雙方都壞。求完好無損的車輛編號。

解題觀察

第 i 輛車完好 當且僅當 第 i 行中不存在 1 或 3。因為 1 表示作為行車被撞，3 表示雙方都壞，兩者都意味著第 i 車受損。列值 2、3 不影響行車完好性（2 只損列車，3 已被行值 3 覆蓋）。

算法

1. 讀入 n。
2. 對每行掃描，若出現 1 或 3 標記該車損壞。
3. 統計未標記車輛，輸出數量與編號。

C++ 代碼

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<bool> bad(n+1, false);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int x; cin >> x;
            if (x == 1 || x == 3) bad[i] = true;
        }
    }
    vector<int> ans;
    for (int i = 1; i <= n; ++i) if (!bad[i]) ans.push_back(i);
    cout << ans.size() << '\n';
    for (int x : ans) cout << x << ' ';
    return 0;
}

複雜度

• 時間：O(n²) 讀入矩陣。
• 空間：O(n) 存儲標記。