Tontti

n,m,k=tuple(map(int,input().split(" ")))
q,l = 0,[input() for _ in range(n)]
z = [[int(s[w]=="*") for w in range(m)] for s in l]
f = [[0 for w in range(m)] for s in l]
from math import ceil
h = ceil(k**.5)//1
c = max(2,h)
r = int(h==1)
for s in l:
    p=[]
    for w in range(m):
        y=int(s[w]=="*")
        p+=[y]
        q+=(y^k^1)*r
    z+=p

v = min(n,m)
for s in range(c,v+1):
    for y in range(s-1,n):
        for x in range(s-1,m):
            u=f[y][x]
            if s == c:
                for i in range(s):
                    for j in range(s):
                        u += z[y-i][x-j]
                f[y][x] = u
            else:
                for i in range(s):
                    u += z[y-s+1][x-i]
                    u += z[y-i][x-s+1]
                u -= z[y-s+1][x-s+1]
                f[y][x] = u
            if u == k:
                q += 1

print(q)

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED