Forgery (Codeforces 1059B)
Tags: Implement, implementation

Student Andrey has been skipping physical education lessons for the whole term, and now he must somehow get a passing grade on this subject. Obviously, it is impossible to do this by legal means, but Andrey doesn't give up. Having obtained an empty certificate from a local hospital, he is going to use his knowledge of local doctor's handwriting to make a counterfeit certificate of illness. However, after writing most of the certificate, Andrey suddenly discovered that doctor's signature is impossible to forge. Or is it?For simplicity, the signature is represented as an $$$n\times m$$$ grid, where every cell is either filled with ink or empty. Andrey's pen can fill a $$$3\times3$$$ square without its central cell if it is completely contained inside the grid, as shown below. xxxx.xxxx Determine whether is it possible to forge the signature on an empty $$$n\times m$$$ grid.

Input: The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n, m \le 1000$$$).Then $$$n$$$ lines follow, each contains $$$m$$$ characters. Each of the characters is either '.', representing an empty cell, or '#', representing an ink filled cell.

Output: If Andrey can forge the signature, output "YES". Otherwise output "NO".You can print each letter in any case (upper or lower).

Note: In the first sample Andrey can paint the border of the square with the center in $$$(2, 2)$$$.In the second sample the signature is impossible to forge.In the third sample Andrey can paint the borders of the squares with the centers in $$$(2, 2)$$$ and $$$(3, 2)$$$:   we have a clear paper: ............  use the pen with center at $$$(2, 2)$$$. ####.####...  use the pen with center at $$$(3, 2)$$$. ############ In the fourth sample Andrey can paint the borders of the squares with the centers in $$$(3, 3)$$$ and $$$(3, 5)$$$.

Sample Inputs:
3 3
###
#.#
###

3 3
###
###
###

4 3
###
###
###
###

5 7
.......
.#####.
.#.#.#.
.#####.
.......

Sample Outputs:
YES

NO

YES

YES

Solution (Python):
def yn1(sa, n, m, i, j):
    if i + 2 > n - 1 or j + 2 > m - 1:
        return 0
    elif sa[i + 1][j] == '#' and sa[i + 2][j] == '#' and (sa[i][j + 1] == '#') and (sa[i][j + 2] == '#') and (sa[i + 2][j + 1] == '#') and (sa[i + 1][j + 2] == '#') and (sa[i + 2][j + 2] == '#'):
        return 1
    else:
        return 0

def yn2(sa, n, m, i, j):
    if j == 0 or j == m - 1 or i + 2 > n - 1:
        return 0
    elif sa[i][j + 1] == '#' and sa[i][j - 1] == '#' and (sa[i + 1][j + 1] == '#') and (sa[i + 1][j - 1] == '#') and (sa[i + 2][j + 1] == '#') and (sa[i + 2][j - 1] == '#') and (sa[i + 2][j] == '#'):
        return 1
    else:
        return 0

def yn3(sa, n, m, i, j):
    if i == 0 or i == n - 1 or j + 2 > m - 1:
        return 0
    elif sa[i + 1][j] == '#' and sa[i - 1][j] == '#' and (sa[i + 1][j + 1] == '#') and (sa[i - 1][j + 1] == '#') and (sa[i + 1][j + 2] == '#') and (sa[i - 1][j + 2] == '#') and (sa[i][j + 2] == '#'):
        return 1
    else:
        return 0

def yn4(sa, n, m, i, j):
    if j - 2 < 0 or i + 2 > n - 1:
        return 0
    elif sa[i][j - 2] == '#' and sa[i][j - 1] == '#' and (sa[i + 1][j - 2] == '#') and (sa[i + 1][j] == '#') and (sa[i + 2][j - 2] == '#') and (sa[i + 2][j - 1] == '#') and (sa[i + 2][j] == '#'):
        return 1
    else:
        return 0

def yn5(sa, n, m, i, j):
    if i - 2 < 0 or j + 2 > m - 1:
        return 0
    elif sa[i - 2][j] == '#' and sa[i - 1][j] == '#' and (sa[i - 2][j + 1] == '#') and (sa[i][j + 1] == '#') and (sa[i - 2][j + 2] == '#') and (sa[i - 1][j + 2] == '#') and (sa[i][j + 2] == '#'):
        return 1
    else:
        return 0

def yn6(sa, n, m, i, j):
    if i == 0 or i == n - 1 or j - 2 < 0:
        return 0
    elif sa[i - 1][j - 1] == '#' and sa[i - 1][j - 2] == '#' and (sa[i - 1][j] == '#') and (sa[i + 1][j - 2] == '#') and (sa[i + 1][j] == '#') and (sa[i + 1][j - 1] == '#') and (sa[i][j - 2] == '#'):
        return 1
    else:
        return 0

def yn7(sa, n, m, i, j):
    if j == 0 or j == m - 1 or i - 2 < 0:
        return 0
    elif sa[i][j - 1] == '#' and sa[i - 1][j - 1] == '#' and (sa[i - 2][j - 1] == '#') and (sa[i - 2][j] == '#') and (sa[i - 1][j + 1] == '#') and (sa[i - 2][j + 1] == '#') and (sa[i][j + 1] == '#'):
        return 1
    else:
        return 0

def yn8(sa, n, m, i, j):
    if j - 2 < 0 or i - 2 < 0:
        return 0
    elif sa[i][j - 1] == '#' and sa[i][j - 2] == '#' and (sa[i - 1][j] == '#') and (sa[i - 1][j - 2] == '#') and (sa[i - 2][j] == '#') and (sa[i - 2][j - 1] == '#') and (sa[i - 2][j - 2] == '#'):
        return 1
    else:
        return 0

def yn(sa, n, m, i, j):
    if yn1(sa, n, m, i, j) or yn2(sa, n, m, i, j) or yn3(sa, n, m, i, j) or yn4(sa, n, m, i, j) or yn5(sa, n, m, i, j) or yn6(sa, n, m, i, j) or yn7(sa, n, m, i, j) or yn8(sa, n, m, i, j):
        return 1
    else:
        return 0
(n, m) = map(int, input().split())
sa = []
for i in range(n):
    s = input()
    sa.append(s)
dp = 1
for i in range(len(sa)):
    for j in range(len(sa[i])):
        if sa[i][j] == '#' and yn(sa, n, m, i, j) == 0:
            dp = 0
            break
    if dp == 0:
        break
if dp == 0:
    print('NO')
else:
    print('YES')

Solution (Python):
(n, m) = (int(i) for i in input().split())
a = []
for i in range(n):
    a.append(list(input()))
bbb = 0
for y in range(n):
    bb = 0
    for x in range(m):
        if a[y][x] != '#':
            continue
        good = 0
        for yy in range(max(0, y - 1), min(y + 2, n)):
            for xx in range(max(0, x - 1), min(x + 2, m)):
                if yy == y and xx == x:
                    continue
                br = 0
                if yy - 1 < 0 or yy + 2 > n or xx - 1 < 0 or (xx + 2 > m):
                    continue
                for yyy in range(yy - 1, yy + 2):
                    for xxx in range(xx - 1, xx + 2):
                        if yyy == yy and xxx == xx:
                            continue
                        if a[yyy][xxx] == '.':
                            br = 1
                            break
                    if br:
                        break
                if not br:
                    for yyy in range(yy - 1, yy + 2):
                        for xxx in range(xx - 1, xx + 2):
                            if yyy == yy and xxx == xx:
                                continue
                            a[yyy][xxx] = '*'
                    good = 1
                    break
            if good:
                break
        if not good:
            bb = 1
            break
    if bb:
        bbb = 1
        break
if bbb:
    print('NO')
else:
    print('YES')

Solution (Python):
(n, m) = [int(x) for x in input().split()]
sign = []
bad = False
for _ in range(n):
    sign.append(input())
for i in range(n):
    if bad:
        break
    for j in range(m):
        if bad:
            break
        if sign[i][j] == '#':
            bad = True
            if 0 < i < n - 1 and sign[i - 1][j] == '#' and (sign[i + 1][j] == '#'):
                if j > 1 and sign[i - 1][j - 1] == '#' and (sign[i - 1][j - 2] == '#') and (sign[i + 1][j - 1] == '#') and (sign[i + 1][j - 2] == '#') and (sign[i][j - 2] == '#'):
                    bad = False
                    continue
                if j + 2 < m and sign[i - 1][j + 1] == '#' and (sign[i - 1][j + 2] == '#') and (sign[i + 1][j + 1] == '#') and (sign[i + 1][j + 2] == '#') and (sign[i][j + 2] == '#'):
                    bad = False
                    continue
            if i > 1 and sign[i - 2][j] == '#':
                if 0 < j < m - 1 and sign[i][j - 1] == '#' and (sign[i][j + 1] == '#') and (sign[i - 1][j - 1] == '#') and (sign[i - 1][j - 1] == '#') and (sign[i - 2][j - 1] == '#') and (sign[i - 2][j - 1] == '#'):
                    bad = False
                    continue
                if j > 1 and sign[i][j - 1] == '#' and (sign[i][j - 2] == '#') and (sign[i - 1][j - 2] == '#') and (sign[i - 1][j] == '#') and (sign[i - 2][j - 1] == '#') and (sign[i - 2][j - 2] == '#'):
                    bad = False
                    continue
                if j + 2 < m and sign[i][j + 1] == '#' and (sign[i][j + 2] == '#') and (sign[i - 1][j + 2] == '#') and (sign[i - 1][j] == '#') and (sign[i - 2][j + 1] == '#') and (sign[i - 2][j + 2] == '#'):
                    bad = False
                    continue
            if i + 2 < n and sign[i + 2][j] == '#':
                if 0 < j < m - 1 and sign[i][j - 1] == '#' and (sign[i][j + 1] == '#') and (sign[i + 1][j - 1] == '#') and (sign[i + 1][j - 1] == '#') and (sign[i + 2][j - 1] == '#') and (sign[i + 2][j - 1] == '#'):
                    bad = False
                    continue
                if j > 1 and sign[i][j - 1] == '#' and (sign[i][j - 2] == '#') and (sign[i + 1][j - 2] == '#') and (sign[i + 1][j] == '#') and (sign[i + 2][j - 1] == '#') and (sign[i + 2][j - 2] == '#'):
                    bad = False
                    continue
                if j + 2 < m and sign[i][j + 1] == '#' and (sign[i][j + 2] == '#') and (sign[i + 1][j + 2] == '#') and (sign[i + 1][j] == '#') and (sign[i + 2][j + 1] == '#') and (sign[i + 2][j + 2] == '#'):
                    bad = False
                    continue
if bad:
    print('NO')
else:
    print('YES')