Codeforces Round 472-2B题解报告

There is a rectangular grid of n rows of m initially-white cells each.

Arkady performed a certain number (possibly zero) of operations on it. In the i-th operation, a non-empty subset of rows Ri and a non-empty subset of columns Ci are chosen. For each row r in Ri and each column c in Ci, the intersection of row r and column c is coloured black.

There’s another constraint: a row or a column can only be chosen at most once among all operations. In other words, it means that no pair of (i, j) (i < j) exists such that or , where denotes intersection of sets, and denotes the empty set.

You are to determine whether a valid sequence of operations exists that produces a given final grid.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 50) — the number of rows and columns of the grid, respectively.

Each of the following n lines contains a string of m characters, each being either ‘.’ (denoting a white cell) or ‘#’ (denoting a black cell), representing the desired setup.

Output

If the given grid can be achieved by any valid sequence of operations, output “Yes”; otherwise output “No” (both without quotes).

You can print each character in any case (upper or lower).

Examples

input
5 8
.#.#..#.
.....#..
.#.#..#.
#.#....#
.....#..
output
Yes
input
5 5
..#..
..#..
#####
..#..
..#..
output
No
input
5 9
........#
#........
..##.#...
.......#.
....#.#.#
output
No

分析

举三个简单的例子。
（1）

3 3
#.#
...
#.#

第一步操作：取R1包含第一行和第三行，C1包含第一列和第三列，则四个#所在的格子就会都被涂成黑色。
所以经过一步操作即能达到结果，输出“Yes”

（2）

3 3
..#
...
#.#

第一步操作：取R1包含第一行和第三行，C1包含第三列，则右上角和右下角的#所在的格子会被涂成黑色。
第二步操作：取R2包含第三行，C2包含第一列，可把左下角的#所在的格子涂成黑色。但是第三行上一步已经被涂过一次了，违反了题目中R1∩R2必须为空的要求，所以结果为”No”

（3）

3 3
#.#
.#.
#.#

第一步操作：取R1包含第一行和第三行，C1包含第一列第三列，则四个角#所在的格子会被涂成黑色。
第二步操作：取R2包含第二行，C2包含第二列，可把中央的#所在的格子涂成黑色。
这样，所有的#所在的格子都被涂成了黑色，并且R1∩R2为空，C1∩C2为空，符合题意，输出”Yes”

思路

观察上面三个例子，可以发现：
如果两行不一样，那么这两行中的#格子所在的列必须也不一样，结果才为”Yes”。比如例（3），第二行和第一行不一样，第二行的#所在的列（第2列）与第一行的#所在的列（第1，3列）也不一样，结果为”Yes”
反过来，如果两行不一样，但是这两行中的#格子所在的列有一样的，相当于是有了交集，结果为”No”。比如例（2）。

代码

#include <cstdio>
typedef long long int64;
static const int MAXN = 53;
static int n, m;
static bool a[MAXN][MAXN];
int main()
{
    scanf("%d%d", &n, &m);
    getchar();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= m; ++j)
        {
            a[i][j] = (getchar() == '#');
        }
    }
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            bool all_same = true, no_intersect = true;
            for (int k = 0; k < m; ++k)
            {
                if (a[i][k] != a[j][k])
                {
                    all_same = false;
                }
                if (a[i][k] && a[j][k])
                {
                    no_intersect = false;
                }
            }
            if (!all_same && !no_intersect)
            {
                puts("No");
                return 0;
            }
        }
    }
    puts("Yes");
    return 0;
}