← 返回题目列表

Codeforces · 924/A

A. 神秘马赛克

中文机器翻译题面 查看原题

有一个矩形网格,由 n 行组成,每行有 m 个最初为白色的单元格。

Arkady 对其执行了一定数量(可能为零)的操作。在第 i 次操作中,选择行 Ri 的非空子集和列 Ci 的非空子集。对于Ri中的每一行r和Ci中的每一列c,行r和列c的交集被涂成黑色。

还有另一个限制:在所有操作中一行或一列最多只能选择一次。换句话说,这意味着不存在满足 $$R_i \cap R_j \neq \varnothing$$ 或 $$C_i \cap C_j \neq \varnothing$$ 的 (i, j) (i < j) 对,其中 ?表示集合的交集,$$\phi$$ 表示空集。

您将确定是否存在产生给定最终网格的有效操作序列。

输入

第一行包含两个以空格分隔的整数 n 和 m (1 ≤ n, m ≤ 50) - 分别是网格的行数和列数。

以下 n 行中的每一行都包含 m 个字符的字符串,每个字符都是“.” (表示白色单元格)或“#”(表示黑色单元格),代表所需的设置。

输出

如果给定的网格可以通过任何有效的操作序列实现,则输出“Yes”;否则输出“No”(均不带引号)。

您可以以任何大小写(大写或小写)打印每个字符。

示例

输入 #1

5 8
.#.#..#.
.....#..
.#.#..#.
#.#....#
.....#..

输出 #1

Yes

输入 #2

5 5
..#..
..#..
#####
..#..
..#..

输出 #2

No

输入 #3

5 9
........#
#........
..##.#...
.......#.
....#.#.#

输出 #3

No

注意

对于第一个示例,可以通过 3 次操作来生成所需的设置,如下所示。

对于第二个示例,无法生成所需的设置,因为为了对中心行进行着色,必须在一次操作中选择第三行和所有列,但此后无法再次选择任何列,因此无法对中心列中的其他单元格进行着色。