Tontti

trees = []
height,width,wantedTrees = [int(x) for x in raw_input().split(" ")]
# Last tiles you can go to in each direction
limits = width-1, height-1

# Find trees from imput and place them to an list.
for y in range(0,height):
	inputRow = raw_input()
	for x in range(0, len(inputRow)):
		if inputRow[x] == '*':
			trees.append((x,y))
			
# Find all possible squares, that are as small as possible.
foundRectangles = []

shorter_smaller = 0
shorter_higher = 0
longer_higher = 0
longer_smaller = 0

for index_1 in range(0,len(trees)):
	for index_2 in range(index_1,len(trees)):
		
		tree_1 = trees[index_1]
		tree_2 = trees[index_2]
		
		longer = 0
		if abs(tree_1[0]-tree_2[0]) < abs(tree_1[1]-tree_2[1]):
			longer = 1
		shorter = (longer + 1) % 2
		
		if tree_1[shorter] >= tree_2[shorter]:
			shorter_higher = tree_1[shorter]
			shorter_smaller = tree_2[shorter]
		else:
			shorter_higher = tree_2[shorter]
			shorter_smaller = tree_1[shorter]
			
		if tree_1[longer] >= tree_2[longer]:
			longer_higher = tree_1[longer]
			longer_smaller = tree_2[longer]
		else:
			longer_higher = tree_2[longer]
			longer_smaller = tree_1[longer]
		
		side = longer_higher - longer_smaller
		max_distance = side - (shorter_higher - shorter_smaller)

		# Shorter is the axis with varying values.
		# Max distance is the max variance from the default position.
		# Longer is the axis that has longer distance beetween the values of the two points.
		# Longer determines the size of the rectangle.
		all_positions = list(range(max(0, max_distance - shorter_smaller), min(max_distance, (limits[shorter]) - shorter_higher)+1))
		# If it is impossible to construct a square with those two trees inside, just continue.
		if len(all_positions)==0:
			continue
		
		
		
		# Find where a new tree enters or leaves the area.
		modifyTrees = dict([(i, 0) for i in all_positions])
		for tree in trees:
			if tree[longer] < longer_smaller or tree[longer] > longer_higher:
				continue
			tree_pos = tree[shorter]
			if tree_pos < shorter_smaller-max_distance+all_positions[0] or tree_pos > shorter_higher+all_positions[-1]:
				continue
			
			# The tree is somewhere in the vicinity of our rectangle. Let's find it!			
			if tree_pos < shorter_smaller - max_distance + all_positions[-1]:
				modifyTrees[tree_pos + max_distance - shorter_smaller + 1] -= 1
				modifyTrees[all_positions[0]] += 1
			elif tree_pos > shorter_higher+all_positions[0]:
			    
				modifyTrees[tree_pos - shorter_higher] += 1
			else:
				modifyTrees[all_positions[0]] += 1
		# Find areas with the correct amount of trees.
		trees_in_area = 0
		for positionModifier in all_positions:
			trees_in_area+=modifyTrees[positionModifier]
			if trees_in_area == wantedTrees:
				if longer == 0:
					rectangle = (longer_smaller,shorter_smaller-max_distance+positionModifier,side)
				else:
					rectangle = (shorter_smaller-max_distance+positionModifier,longer_smaller,side)
				if rectangle not in foundRectangles:
					foundRectangles.append(rectangle)
# Now, for every small rectangle, try to make it larger in each direction.
lFR = []

def tryLargerRectangles(rectangle):
	side = rectangle[2]+1
	recX=rectangle[0]
	recY=rectangle[1]
	for dxy in [(-1,-1),(-1,0),(0,-1),(0,0)]:
		newX = recX
		newY = recY
		
		newRecX=recX+dxy[0]
		newRecY=recY+dxy[1]
		
		if dxy[0]==0:
			newX+=side
		else:
			newX-=1
		if dxy[1]==0:
			newY+=side
		else:
			newY-=1
		
		if newX < 0 or newX > limits[0] or newY < 0 or newY > limits[1]:
			continue
		
		conflict = False
		for tree in trees:
			tree_x = tree[0]
			tree_y = tree[1]
			if (tree_x == newX and tree_y >= newRecY and tree_y <= newRecY+side) or (tree_y == newY and tree_x >= newRecX and tree_x <= newRecX+side):
				conflict = True
				break
		
		if not conflict:
			newRec = (newRecX,newRecY,side)
			if newRec not in lFR:
				lFR.append(newRec)
				tryLargerRectangles(newRec)


for rectangle in foundRectangles:
	tryLargerRectangles(rectangle)

print len(lFR)+len(foundRectangles)
		

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: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 131, in <module>
    tryLargerRectangles(rectangle)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(ne...

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: RUNTIME ERROR

Test 14

Group: 3

Verdict: RUNTIME ERROR

Test 15

Group: 3

Verdict: RUNTIME ERROR