L-shapes (Codeforces 1722F)
Tags: Implement, dfs and similar

An L-shape is a figure on gridded paper that looks like the first four pictures below. An L-shape contains exactly three shaded cells (denoted by *), which can be rotated in any way.  You are given a rectangular grid. Determine if it contains L-shapes only, where L-shapes can't touch an edge or corner. More formally:   Each shaded cell in the grid is part of exactly one L-shape, and  no two L-shapes are adjacent by edge or corner. For example, the last two grids in the picture above do not satisfy the condition because the two L-shapes touch by corner and edge, respectively.

Input: The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 50$$$) — the number of rows and columns in the grid, respectively.Then $$$n$$$ lines follow, each containing $$$m$$$ characters. Each of these characters is either '.' or '*' — an empty cell or a shaded cell, respectively.

Output: For each test case, output "YES" if the grid is made up of L-shape that don't share edges or corners, and "NO" otherwise.You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).


Sample Inputs:
10
6 10
........**
.**......*
..*..*....
.....**...
...*.....*
..**....**
6 10
....*...**
.**......*
..*..*....
.....**...
...*.....*
..**....**
3 3
...
***
...
4 4
.*..
**..
..**
..*.
5 4
.*..
**..
....
..**
..*.
3 2
.*
**
*.
2 3
*..
.**
3 2
..
**
*.
3 3
.**
*.*
**.
3 3
..*
.**
..*

Sample Outputs:
YES
NO
NO
NO
YES
NO
NO
YES
NO
NO

Solution (Python):
for i in range(int(input())):
    (n, m) = map(int, input().split())
    M = [['.' for j in range(m + 2)]]
    for j in range(n):
        M.append(['.'] + list(input()) + ['.'])
    M.append(['.' for j in range(m + 2)])
    v = True
    for j in range(1, n + 1):
        for k in range(1, m + 1):
            if M[j][k] == '*':
                L = []
                if M[j - 1][k - 1] == '*':
                    L.append((j - 1, k - 1))
                if M[j - 1][k] == '*':
                    L.append((j - 1, k))
                if M[j - 1][k + 1] == '*':
                    L.append((j - 1, k + 1))
                if M[j + 1][k - 1] == '*':
                    L.append((j + 1, k - 1))
                if M[j + 1][k] == '*':
                    L.append((j + 1, k))
                if M[j + 1][k + 1] == '*':
                    L.append((j + 1, k + 1))
                if M[j][k + 1] == '*':
                    L.append((j, k + 1))
                if M[j][k - 1] == '*':
                    L.append((j, k - 1))
                if len(L) != 2 or max(abs(L[0][0] - L[1][0]), abs(L[0][1] - L[1][1])) > 1:
                    v = False
                    print('NO')
                    break
        if not v:
            break
    if v:
        print('YES')

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
ip = sys.stdin.readline
op = sys.stdout.write
t = int(ip())
res = []
for _ in range(t):
    (row, col) = [int(x) for x in ip().split()]
    grid = []
    for i in range(row):
        curr_row = ip()
        cr = []
        for char in curr_row:
            cr.append(char)
        grid.append(cr)
    is_valid = True
    for i in range(row):
        for j in range(col):
            if grid[i][j] != '*':
                continue
            configure = -1
            if i + 1 < row and grid[i + 1][j] == '*' and (j + 1 < col) and (grid[i + 1][j + 1] == '*'):
                configure = 1
                grid[i][j] = '#'
                grid[i + 1][j] = '#'
                grid[i + 1][j + 1] = '#'
            elif i + 1 < row and grid[i + 1][j] == '*' and (j - 1 >= 0) and (grid[i + 1][j - 1] == '*'):
                configure = 2
                grid[i][j] = '#'
                grid[i + 1][j] = '#'
                grid[i + 1][j - 1] = '#'
            elif j + 1 < col and grid[i][j + 1] == '*' and (i + 1 < row) and (grid[i + 1][j + 1] == '*'):
                configure = 3
                grid[i][j] = '#'
                grid[i][j + 1] = '#'
                grid[i + 1][j + 1] = '#'
            elif j + 1 < col and grid[i][j + 1] == '*' and (i + 1 < row) and (grid[i + 1][j] == '*'):
                configure = 4
                grid[i][j] = '#'
                grid[i][j + 1] = '#'
                grid[i + 1][j] = '#'
            if configure == -1:
                is_valid = False
                break
            if configure == 1:
                dirs = [(-1, 0), (-1, 1), (0, 2), (0, 1), (-1, -1), (0, -1), (1, -1), (2, -1), (2, 0), (2, 1), (2, 2), (1, 2)]
                for (a, b) in dirs:
                    x = i + a
                    y = j + b
                    if 0 <= x < row and 0 <= y < col and (grid[x][y] == '#'):
                        is_valid = False
                        break
            elif configure == 2:
                dirs = [(-1, 0), (-1, 1), (0, 1), (0, -1), (1, 1), (2, 1), (2, 0), (2, -1), (2, -2), (1, -2), (0, -2), (-1, -1)]
                for (a, b) in dirs:
                    x = i + a
                    y = j + b
                    if 0 <= x < row and 0 <= y < col and (grid[x][y] == '#'):
                        is_valid = False
                        break
            elif configure == 3:
                dirs = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (-1, 1), (-1, 2), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
                for (a, b) in dirs:
                    x = i + a
                    y = j + b
                    if 0 <= x < row and 0 <= y < col and (grid[x][y] == '#'):
                        is_valid = False
                        break
            elif configure == 4:
                dirs = [(-1, 0), (-1, -1), (0, -1), (1, -1), (2, -1), (2, 0), (2, 1), (-1, 1), (-1, 2), (0, 2), (1, 2), (1, 1)]
                for (a, b) in dirs:
                    x = i + a
                    y = j + b
                    if 0 <= x < row and 0 <= y < col and (grid[x][y] == '#'):
                        is_valid = False
                        break
        if not is_valid:
            break
    if is_valid:
        res.append('YES')
    else:
        res.append('NO')
for val in res:
    op(val + '\n')

Solution (Python):
""""""
import sys

def adjR(r, c, ls, m, n):
    count = 0
    ret = [-1, 0, 0, 0, 0]
    if c + 1 == n:
        pass
    elif ls[r][c + 1] == '*':
        count += 1
        ret[1] = 1
    if c == 0:
        pass
    elif ls[r][c - 1] == '*':
        count += 1
        ret[2] = 1
    if r == 0:
        pass
    elif ls[r - 1][c] == '*':
        count += 1
        ret[3] = 1
    if r + 1 == m:
        pass
    elif ls[r + 1][c] == '*':
        count += 1
        ret[4] = 1
    ret[0] = count
    return ret

def adjC(r, c, ls, m, n):
    count = 0
    ret = [-1, 0, 0, 0, 0]
    if r + 1 == m or c + 1 == n:
        pass
    elif ls[r + 1][c + 1] == '*':
        count += 1
        ret[4] = 1
    if c == 0:
        pass
    else:
        try:
            if ls[r + 1][c - 1] == '*':
                count += 1
                ret[3] = 1
        except:
            pass
    if c == 0 or r == 0:
        pass
    elif ls[r - 1][c - 1] == '*':
        count += 1
        ret[1] = 1
    if r == 0 or c == n:
        pass
    else:
        try:
            if ls[r - 1][c + 1] == '*':
                count += 1
                ret[2] = 1
        except:
            pass
    ret[0] = count
    return ret
for _ in range(int(sys.stdin.readline())):
    (row, col) = map(int, sys.stdin.readline().split())
    bigls = []
    for i in range(row):
        s = sys.stdin.readline().strip()
        bigls.append(list(s))
    f = False
    for r in range(row):
        for c in range(col):
            if bigls[r][c] == '*':
                rowret = adjR(r, c, bigls, row, col)
                colret = adjC(r, c, bigls, row, col)
                if rowret[0] + colret[0] != 2:
                    f = True
                    break
                elif rowret[0] == 0:
                    f = True
                    break
                if colret[0] == 0:
                    if rowret[1] == rowret[2] == 1 or rowret[3] == rowret[4] == 1:
                        f = True
                        break
                    continue
                if rowret[1] == 1:
                    if colret[2] + colret[4] != 1:
                        f = True
                        break
                    continue
                if rowret[2] == 1:
                    if colret[1] + colret[3] != 1:
                        f = True
                        break
                    continue
                if rowret[3] == 1:
                    if colret[1] + colret[2] != 1:
                        f = True
                        break
                    continue
                if rowret[4] == 1:
                    if colret[3] + colret[4] != 1:
                        f = True
                        break
                    continue
                continue
        if f:
            break
    if f:
        print('no')
        continue
    print('yes')