Find the Spruce (Codeforces 1461B)
Tags: DP, brute force

Holidays are coming up really soon. Rick realized that it's time to think about buying a traditional spruce tree. But Rick doesn't want real trees to get hurt so he decided to find some in an $$$n \times m$$$ matrix consisting of "*" and ".".  To find every spruce first let's define what a spruce in the matrix is. A set of matrix cells is called a spruce of height $$$k$$$ with origin at point $$$(x, y)$$$ if:  All cells in the set contain an "*".  For each $$$1 \le i \le k$$$ all cells with the row number $$$x+i-1$$$ and columns in range $$$[y - i + 1, y + i - 1]$$$ must be a part of the set. All other cells cannot belong to the set.  Examples of correct and incorrect spruce trees:  Now Rick wants to know how many spruces his $$$n \times m$$$ matrix contains. Help Rick solve this problem.

Input: Each test contains one or more test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$).The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 500$$$) — matrix size.Next $$$n$$$ lines of each test case contain $$$m$$$ characters $$$c_{i, j}$$$ — matrix contents. It is guaranteed that $$$c_{i, j}$$$ is either a "." or an "*".It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$500^2$$$ ($$$\sum n \cdot m \le 500^2$$$).

Output: For each test case, print single integer — the total number of spruces in the matrix.

Note: In the first test case the first spruce of height $$$2$$$ has its origin at point $$$(1, 2)$$$, the second spruce of height $$$1$$$ has its origin at point $$$(1, 2)$$$, the third spruce of height $$$1$$$ has its origin at point $$$(2, 1)$$$, the fourth spruce of height $$$1$$$ has its origin at point $$$(2, 2)$$$, the fifth spruce of height $$$1$$$ has its origin at point $$$(2, 3)$$$.In the second test case the first spruce of height $$$1$$$ has its origin at point $$$(1, 2)$$$, the second spruce of height $$$1$$$ has its origin at point $$$(2, 1)$$$, the third spruce of height $$$1$$$ has its origin at point $$$(2, 2)$$$.

Sample Inputs:
4
2 3
.*.
***
2 3
.*.
**.
4 5
.***.
*****
*****
*.*.*
5 7
..*.*..
.*****.
*******
.*****.
..*.*..

Sample Outputs:
5
3
23
34

Solution (Python):
I = input
for _ in [0] * int(I()):
    a = [I() for _ in [0] * int(I().split()[0])]
    b = [0] * 501
    r = 0
    for s in a[::-1]:
        b = (0, *(x < '.' and min(b[i:i + 3]) + 1 for (i, x) in enumerate(s)), 0)
        r += sum(b)
    print(r)

Solution (Python):
import random
import math
from collections import defaultdict
import itertools
from sys import stdin, stdout
import sys
import operator
from decimal import Decimal
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def main():
    mod = 10 ** 9 + 7
    for _ in range(int(input())):
        (n, m) = list(map(int, input().split()))
        c = []
        for _ in range(n):
            c.append(input())
        pt = [0] * m
        ans = 0
        for i in range(n):
            ct = [0] * m
            j = 0
            while j < m:
                if c[i][j] == '*':
                    start = j
                    while j < m and c[i][j] == '*':
                        j += 1
                    for k in range(start, j):
                        ct[k] = min(pt[k] + 1, k + 1 - start, j - k)
                j += 1
            pt = ct.copy()
            ans += sum(ct)
        print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import random
import math
from collections import defaultdict
import itertools
from sys import stdin, stdout
import sys
import operator
from decimal import Decimal
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def main():
    mod = 10 ** 9 + 7
    for _ in range(int(input())):
        (n, m) = list(map(int, input().split()))
        c = []
        for _ in range(n):
            c.append(input())
        pt = [0] * m
        ans = 0
        for i in range(n):
            ct = [0] * m
            j = 0
            while j < m:
                if c[i][j] == '*':
                    start = j
                    while c[i][j] == '*':
                        j += 1
                        if j > m - 1:
                            break
                    end = j
                    l = end - start
                    mid = start + (l + 1) // 2
                    for k in range(start, mid):
                        ct[k] = min(pt[k] + 1, k + 1 - start)
                    for k in range(mid, end):
                        ct[k] = min(pt[k] + 1, end - k)
                else:
                    j += 1
            pt = ct.copy()
            ans += sum(ct)
        print(ans)
if __name__ == '__main__':
    main()