Madoka and the Elegant Gift (Codeforces 1647B)
Tags: Others, graphs

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 \le t \le 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 \le n, m \le 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).

Note: In the second test case the table is not elegant, because the red and the purple subrectangles are nice and intersect.   In the fourth test case the table is not elegant, because the red and the purple subrectangles are nice and intersect.   

Sample Inputs:
5
3 3
100
011
011
3 3
110
111
110
1 5
01111
4 5
11111
01010
01000
01000
3 2
11
00
11

Sample Outputs:
YES
NO
YES
NO
YES

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    (n, m) = map(int, readline().split())
    g = [list(map(int, str(readline()))) for _ in range(n)]
    for i in range(n - 1):
        for j in range(m - 1):
            cnt = g[i][j] + g[i][j + 1] + g[i + 1][j] + g[i + 1][j + 1]
            if cnt == 3:
                print('NO')
                return
    print('YES')

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    (N, M) = map(int, input().split())
    arr = []
    for i in range(N):
        a1 = input()
        arr.append(a1)
    i = 0
    while i < N - 1:
        j = 0
        while j < M - 1:
            a1 = arr[i][j]
            a2 = arr[i][j + 1]
            a3 = arr[i + 1][j]
            a4 = arr[i + 1][j + 1]
            if a1 == '1' and a2 == '0' and (a3 == '1') and (a4 == '1'):
                return 'NO'
            elif a1 == '0' and a2 == '1' and (a3 == '1') and (a4 == '1'):
                return 'NO'
            elif a1 == '1' and a2 == '1' and (a3 == '1') and (a4 == '0'):
                return 'NO'
            elif a1 == '1' and a2 == '1' and (a3 == '0') and (a4 == '1'):
                return 'NO'
            j += 1
        i += 1
    return 'YES'
remained_test_Cases = 1
remained_test_Cases = int(input())
while remained_test_Cases > 0:
    print(solve())
    remained_test_Cases -= 1

Solution (Python):
case = int(input())
for i in range(case):
    tables = input().split(' ')
    n = int(tables[0])
    m = int(tables[1])
    lines = []
    for j in range(n):
        line = input()
        lines.append(line)
    if n == 1 or m == 1:
        print('YES')
        continue
    for j in range(n - 1):
        line1 = lines[j]
        line2 = lines[j + 1]
        printed_flag = False
        state = 0
        for k in range(m):
            temp_state = 0
            same_is = line1[k] == line2[k]
            if not same_is:
                temp_state = 2
            elif line1[k] == '1':
                temp_state = 1
            if temp_state + state == 3:
                print('NO')
                printed_flag = True
                break
            state = temp_state
        if printed_flag:
            break
    if not printed_flag:
        print('YES')