Codeforces Round #777 (Div2) - B.Madoka and the Elegant Gift

문제

Madoka's father just reached 1 million subscribers on Mathub! So the website decided to send him a personalized award — The Mathhub's Bit Button! 

The Bit Button is a rectangular table with n rows and 𝑚m columns with 0 or 1 in each cell. After exploring the table Madoka found out that:

• A subrectangle A is contained in a subrectangle B if there's no cell contained in A but not contained in B.
• Two subrectangles intersect if there is a cell contained in both of them.
• A subrectangle is called black if there's no cell with value 0 inside it.
• A subrectangle is called nice if it's black and it's not contained in another black subrectangle.
• The table is called elegant if there are no two nice intersecting subrectangles.

For example, in the first illustration the red subrectangle is nice, but in the second one it's not, because it's contained in the purple subrectangle.

Help Madoka to determine whether the table is elegant.

Input

Each test contains multiple test cases. The first line contains a single integer t (1≤t≤200) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two positive integers n,m (1≤n,m≤100).

The next 𝑛n lines contain strings of length 𝑚m consisting of zeros and ones — the description of the table.

It is guaranteed that the sum of the values of n and the sum of the values of 𝑚m for all test cases do not exceed 777.

Output

For each test case print "YES" if its table is elegant or print "NO" otherwise.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

---

풀이

참... 코드포스 잘푸는 사람들 보면 신기하다. 어떻게 새벽까지 그런 집중력을 보일 수 있는지 ㅋㅋ.

항상 느끼는 것이지만 알고리즘 문제를 풀 때는 감으로 대충 풀면 망한다. 느리더라도 문제를 완벽히 이해하고 풀어야 한다. 나는 안그래도 독해력이 딸리는데 영어 해석까지 하려고 하니 매번 코포 문제를 풀 때마다 조급해서 대충 해석하고 풀다가 망한다. 이번 문제도 빨리 풀어야 한다는 생각 때문에 틀린 방법으로 접근하여 삽질만 1시간 반정도 했고 멘탈이 터져 빡종했다 ㅋㅋ.

 

아무튼 이 문제를 요약하자면 1이 직사각형 모양을 띄고 있다면 "YES"를 아니라면 "NO"를 출력하는 문제이다.

10000  10000
01111  01111
01111  01111
10000  10010

 

 예를 들어 왼쪽은 1들이 모두 직사각형을 이루고 있어 "YES"를 출력하지만 오른쪽은 마지막줄에 2번째 1때문에 조건을 만족하지 못하여 "NO"를 출력해야 한다.

 

1들이 모두 직사각형을 이루고 있는지 확인하는 것이 이 문제의 핵심이었다. 현재 문자열과 아래 문자열을 한 글자씩 비교했을 때 둘 다 1이라면 양 옆의 문자도 비교하여 다르다면 직사각형이 아니라는 의미이므로 "NO"를 출력하면 된다.

 

1. 현재 문자열과 아래 문자열을 한 문자씩 비교한다.
2. 만약 두 문자 모두 1이라면 앙 옆의 문자를 비교하고 다르다면 "NO"를 출력하고 return한다.
3. 1,2를 N-1번 만큼 반복하고 "YES"를 출력한다.

 

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long
#define p(a,b) make_pair(a,b)
using namespace std;



void input() {
}

void init() {
}


void solution() {
    int N,M; cin>>N>>M;
    vector<string> v;
    v.resize(N);
    
    for(int i=0;i<N;i++){
        cin>>v[i];
    }
    
    for(int i=0;i<N-1;i++){
        for(int j=0;j<M;j++){
            // 현재 문자열과 아래 문자열의 글자가 모두 1인 경우
            if(v[i][j]=='1'&&v[i+1][j]=='1'){
                //양 옆의 글자가 다르다면 "NO"를 출력하고 return한다.
                if(j-1>=0&&v[i][j-1]!=v[i+1][j-1]){
                    cout<<"NO"<<endl;
                    return;
                }
                if(j+1<M&&v[i][j+1]!=v[i+1][j+1]){
                    cout<<"NO"<<endl;
                    return;
                }
            }
        }
    }
    
    cout<<"YES"<<endl;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin>>T;
    while(T--)
        solution();
    return 0;
}