How Many Squares? (Codeforces 11C)
Tags: Implement, implementation

You are given a 0-1 rectangular matrix. What is the number of squares in it? A square is a solid square frame (border) with linewidth equal to 1. A square should be at least 2 × 2. We are only interested in two types of squares:   squares with each side parallel to a side of the matrix;  squares with each side parallel to a diagonal of the matrix. For example the following matrix contains only one square of the first type: 0000000 0111100 0100100 0100100 0111100The following matrix contains only one square of the second type:00000000010000010100000100000000000Regardless of type, a square must contain at least one 1 and can't touch (by side or corner) any foreign 1. Of course, the lengths of the sides of each square should be equal.How many squares are in the given matrix?

Input: The first line contains integer t (1 ≤ t ≤ 10000), where t is the number of test cases in the input. Then test cases follow. Each case starts with a line containing integers n and m (2 ≤ n, m ≤ 250), where n is the number of rows and m is the number of columns. The following n lines contain m characters each (0 or 1).The total number of characters in all test cases doesn't exceed 106 for any input file.

Output: You should output exactly t lines, with the answer to the i-th test case on the i-th line.


Sample Inputs:
2
8 8
00010001
00101000
01000100
10000010
01000100
00101000
11010011
11000011
10 10
1111111000
1000001000
1011001000
1011001010
1000001101
1001001010
1010101000
1001001000
1000001000
1111111000

1
12 11
11111111111
10000000001
10111111101
10100000101
10101100101
10101100101
10100000101
10100000101
10111111101
10000000001
11111111111
00000000000

Sample Outputs:
1
2

3

Solution (Python):
import sys
input = sys.stdin.readline

def find(x):
    while Group[x] != x:
        x = Group[x]
    return x

def Union(x, y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)

def calc(i, j, x):
    flag = 1
    if i + x < n and j + x < m:
        for k in range(x + 1):
            if MAP[i + k][j] == '0':
                flag = 0
                break
            if MAP[i][j + k] == '0':
                flag = 0
                break
            if MAP[i + k][j + x] == '0':
                flag = 0
                break
            if MAP[i + x][j + k] == '0':
                flag = 0
                break
    else:
        flag = 0
    if flag == 1:
        return True
    if j - x >= 0 and j + x < m and (i + x + x < n):
        for k in range(x + 1):
            if MAP[i + k][j + k] == '0':
                return False
            if MAP[i + k][j - k] == '0':
                return False
            if MAP[i + 2 * x - k][j + k] == '0':
                return False
            if MAP[i + 2 * x - k][j - k] == '0':
                return False
        return True
    else:
        return False
LANS = []
t = int(input())
for tests in range(t):
    (n, m) = map(int, input().split())
    MAP = [input().strip() for i in range(n)]
    Group = [i for i in range(n * m)]
    Nodes = [1] * (n * m)
    for i in range(n):
        for j in range(m):
            if MAP[i][j] == '1':
                if i + 1 < n and MAP[i + 1][j] == '1':
                    Union(i * m + j, (i + 1) * m + j)
                if j + 1 < m and MAP[i][j + 1] == '1':
                    Union(i * m + j, i * m + j + 1)
                if i + 1 < n and j + 1 < m and (MAP[i + 1][j + 1] == '1'):
                    Union(i * m + j, (i + 1) * m + j + 1)
                if i + 1 < n and j - 1 >= 0 and (MAP[i + 1][j - 1] == '1'):
                    Union(i * m + j, (i + 1) * m + j - 1)
    USE = [0] * (n * m)
    ANS = 0
    for i in range(n):
        for j in range(m):
            if MAP[i][j] == '1' and USE[find(i * m + j)] == 0:
                USE[find(i * m + j)] = 1
                if Nodes[find(i * m + j)] % 4 == 0:
                    x = Nodes[find(i * m + j)] // 4
                    if calc(i, j, x) == True:
                        ANS += 1
    LANS.append(ANS)
print('\n'.join(map(str, LANS)))

Solution (Python):
def seed_filling(a, n, m):
    b = [[0] * m for i in range(n)]
    now_label = 0
    for i in range(n):
        for j in range(m):
            if a[i][j] == '1' and b[i][j] == 0:
                now_label += 1
                b[i][j] = now_label
                stack = [[i, j]]
                while len(stack) != 0:
                    (i1, j1) = stack.pop()
                    (i2, j2) = (i1 - 1, j1 - 1)
                    if i2 >= 0 and j2 >= 0:
                        if a[i2][j2] == '1' and b[i2][j2] == 0:
                            b[i2][j2] = now_label
                            stack.append([i2, j2])
                    (i2, j2) = (i1 - 1, j1)
                    if i2 >= 0:
                        if a[i2][j2] == '1' and b[i2][j2] == 0:
                            b[i2][j2] = now_label
                            stack.append([i2, j2])
                    (i2, j2) = (i1 - 1, j1 + 1)
                    if i2 >= 0 and j2 <= m - 1:
                        if a[i2][j2] == '1' and b[i2][j2] == 0:
                            b[i2][j2] = now_label
                            stack.append([i2, j2])
                    (i2, j2) = (i1, j1 - 1)
                    if j2 >= 0:
                        if a[i2][j2] == '1' and b[i2][j2] == 0:
                            b[i2][j2] = now_label
                            stack.append([i2, j2])
                    (i2, j2) = (i1, j1 + 1)
                    if j2 <= m - 1:
                        if a[i2][j2] == '1' and b[i2][j2] == 0:
                            b[i2][j2] = now_label
                            stack.append([i2, j2])
                    (i2, j2) = (i1 + 1, j1 - 1)
                    if i2 <= n - 1 and j2 >= 0:
                        if a[i2][j2] == '1' and b[i2][j2] == 0:
                            b[i2][j2] = now_label
                            stack.append([i2, j2])
                    (i2, j2) = (i1 + 1, j1)
                    if i2 <= n - 1:
                        if a[i2][j2] == '1' and b[i2][j2] == 0:
                            b[i2][j2] = now_label
                            stack.append([i2, j2])
                    (i2, j2) = (i1 + 1, j1 + 1)
                    if i2 <= n - 1 and j2 <= m - 1:
                        if a[i2][j2] == '1' and b[i2][j2] == 0:
                            b[i2][j2] = now_label
                            stack.append([i2, j2])
    return b

def is_sqaure(c):
    lastj = None
    first_row_width = 0
    for c1 in c:
        if c1[0] == c[0][0]:
            if lastj is not None and lastj != c1[1] - 1:
                return 0
            lastj = c1[1]
            first_row_width += 1
        if c1[0] != c[0][0]:
            break
    if first_row_width == 1:
        height = c[-1][0] - c[0][0]
        if height < 2:
            return 0
        if height % 2 != 0:
            return 0
        if len(c) != height * 2:
            return 0
        for c1 in c:
            lin = c1[0] - c[0][0]
            if lin <= height // 2:
                if c1[1] != c[0][1] - lin and c1[1] != c[0][1] + lin:
                    return 0
            elif c1[1] != c[0][1] - (height - lin) and c1[1] != c[0][1] + (height - lin):
                return 0
    if first_row_width > 1:
        height = c[-1][0] - c[0][0]
        if height < 1:
            return 0
        if len(c) != height * 4:
            return 0
        for c1 in c:
            lin = c1[0] - c[0][0]
            if lin == 0 or lin == height:
                if c1[1] - c[0][1] < 0 or c1[1] - c[0][1] > height:
                    return 0
            elif c1[1] - c[0][1] != 0 and c1[1] - c[0][1] != height:
                return 0
    return 1
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for k in range(t):
    a = []
    (n, m) = map(int, input().split())
    for i in range(n):
        a.append(str(input(), 'utf-8')[:-2])
    b = seed_filling(a, n, m)
    c = {}
    for i in range(n):
        for j in range(m):
            if b[i][j] > 0:
                if b[i][j] in c:
                    c[b[i][j]].append([i, j])
                else:
                    c[b[i][j]] = [[i, j]]
    out = 0
    for key in c:
        if is_sqaure(c[key]):
            out += 1
    print(out)

Solution (Python):
import sys

def chk2(s1, s2, i):
    if s1[i] == 49:
        return (4, False, False)
    left = right = False
    cnt = 0
    if i != 0 and s1[i - 1] == 49:
        cnt += 1
        if i - 2 < 0 or s1[i - 2] == s2[i - 2] == 48:
            left = True
    if i != m - 1 and s1[i + 1] == 49:
        cnt += 1
        if i + 2 >= m or s1[i + 2] == s2[i + 2] == 48:
            right = True
    return (cnt, left, right)
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
    (n, m) = [*map(int, input().split())]
    res = 0
    valid1 = []
    valid2 = []
    pending = []
    last = b'0' * m
    for i in range(n):
        cur = input()
        cur1 = []
        cur2 = []
        for (l, r) in pending:
            if set(cur[max(l - 1, 0):min(r + 2, m)]) == {48}:
                res += 1
        pending.clear()
        for (l, r, r0) in valid1:
            flag = False
            if i - r0 == r - l:
                pool1 = set(cur[l:r + 1])
                pool0 = set()
                flag = True
            elif i - r0 in {1, r - l - 1}:
                pool1 = {cur[l], cur[r]}
                pool0 = set(cur[l + 1:r])
            else:
                pool1 = {cur[l], cur[r]}
                pool0 = {cur[l + 1], cur[r - 1]} if r - l != 1 else set()
            pool0 |= {48 if l == 0 else cur[l - 1], 48 if r == m - 1 else cur[r + 1]}
            if pool1 == {49} and pool0 == {48}:
                if flag:
                    pending.append([l, r])
                else:
                    cur1.append([l, r, r0])
        for (l, r, flag) in valid2:
            if r - l == 2:
                if cur[l + 1] == 49 and cur[l] == cur[r] == 48 and (l == 0 or cur[l - 1] == 48) and (r == m - 1 or cur[r + 1] == 48):
                    pending.append([l + 1, l + 1])
            if l == r:
                (c, ll, rr) = chk2(cur, last, l)
                if ll and rr:
                    cur2.append([l - 1, l + 1, True])
            else:
                (lc, ll, lr) = chk2(cur, last, l)
                (rc, rl, rr) = chk2(cur, last, r)
                if lc == rc == 1:
                    if lr and rl:
                        cur2.append([l + 1, r - 1, False])
                    elif ll and rr and flag:
                        cur2.append([l - 1, r + 1, True])
        j = 0
        while j < m:
            while j < m and cur[j] == 48:
                j += 1
            l = j
            while j < m and cur[j] == 49:
                j += 1
            if j - l == 1:
                if l not in {0, m - 1} and set(last[l - 1:l + 2]) == {48}:
                    cur2.append([l, l, True])
            elif l != m:
                if set(last[max(0, l - 1):min(j + 1, m)]) == {48}:
                    cur1.append([l, j - 1, i])
        last = cur
        valid1 = cur1
        valid2 = cur2
    print(res + len(pending))