Codeforces Round 472-2B题解报告

谁践踏了优雅 2022-05-28 01:53 253阅读 0赞

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;
    }

> Codeforces & TopCoder QQ交流群：648202993  
> 更多内容请关注微信公众号  
> ![feicuisenlin\_12x12.jpg][feicuisenlin_12x12.jpg]

[feicuisenlin_12x12.jpg]: /images/20220528/c8c4ca1ae8fc48b9bb7504853c388c4d.png