CF985B Switches and Lamps

你有 $n$ 个开关和 $m$ 盏灯。第 $i$ 个开关可以点亮某些灯。这个信息通过一个 $n$ 行 $m$ 列的矩阵 $a$ 给出，其中 $a_{i,j}=1$ 表示第 $i$ 个开关可以点亮第 $j$ 盏灯，$a_{i,j}=0$ 表示第 $i$ 个开关没有连接到第 $j$ 盏灯。 最开始所有 $m$ 盏灯都是关闭的。 开关只能从“关”变为“开”。也就是说，如果你按下两个或更多个与同一盏灯相连的开关，那么只要按下其中任意一个，该灯就会被点亮，并且之后无论再按下与该灯相连的其他开关，该灯的状态都不会改变。 保证如果你按下所有 $n$ 个开关，所有 $m$ 盏灯都会被点亮。 你觉得开关太多了，想忽略其中一个开关。 你的任务是判断是否存在这样一个开关，使得如果你忽略（不使用）它，但按下剩下的 $n-1$ 个开关，所有 $m$ 盏灯依然都会被点亮。

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2000$），分别表示开关的数量和灯的数量。 接下来的 $n$ 行，每行包含 $m$ 个字符。第 $i$ 行第 $j$ 个字符 $a_{i,j}$ 等于 '1' 表示第 $i$ 个开关可以点亮第 $j$ 盏灯，等于 '0' 表示没有连接。 保证如果你按下所有 $n$ 个开关，所有 $m$ 盏灯都会被点亮。

如果存在这样一个开关，使得忽略它并按下剩下的 $n-1$ 个开关后，所有 $m$ 盏灯仍然都会被点亮，输出 "YES"。如果不存在这样的开关，输出 "NO"。

由 ChatGPT 4.1 翻译