Switches and Lamps 题解

题目传送门

一道枚举题。

首先我们需要知道什么开关才能被去掉，题目要求去掉这个开关后所有的灯依然能够开启。也就是说，这个开关能打开的所有灯都可以由其它开关代替。

思路清晰了，就比较好做。我们可以用一个数组存储下每一盏灯可以被几个开关开启，如果有一盏灯只能被 \(1\) 个开关所开启，则那个开关不能被去掉。

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n, m;
char a[2005][2005];
int cnt[2005]; // cnt[i] 表示有多少个开关可以打开第 i 盏灯
signed main() {
    ios :: sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] == '1') cnt[j]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        bool flag = 0;
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '1') {
                if (cnt[j] == 1) flag = 1; // 这个开关是不可去掉的
            }
        }
        if (!flag) {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    return 0;
}