Tontti

import java.util.*;
 
public class TonttiTehtava {
 
    public static void main(String[] args) {
        IO io = new IO();
        final int height = io.nextInt();
        final int width = io.nextInt();
        final int idealAmountOfTrees = io.nextInt();
 
        List<MatrixElement> trees = new ArrayList<>();
 
        for (int i = 0; i < height; i++) {
            String row = io.next();
            for (int j = 0; j < width; j++) {
                if (row.charAt(j) == '*') {
                    trees.add(new MatrixElement(i, j));
                }
            }
        }
 
        final int amountOfTrees = trees.size();
        final int minSize = (int) Math.ceil(Math.sqrt(idealAmountOfTrees));
        final double density = amountOfTrees / (height * width);
        final int averageSize = (int) Math.round(Math.sqrt(idealAmountOfTrees / density));
 
        int waysOfChoosing = 0;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                int maxSize = Math.min(height - i, width - j);
                int treesInAverageSquare = 0;
                for (int k = 0; k < amountOfTrees; k++) {
                    int withinSquare = trees.get(k).withinSquare(i, j, averageSize);
                    if (withinSquare == 1) treesInAverageSquare++;
                    else if (withinSquare == -1) break;
                }
                if (treesInAverageSquare < idealAmountOfTrees) {
                    waysOfChoosing += checkHigher(trees, idealAmountOfTrees, i, j, averageSize, minSize, maxSize);
                } else if (treesInAverageSquare > idealAmountOfTrees) {
                    waysOfChoosing += checkLower(trees, idealAmountOfTrees, i, j, averageSize, minSize, maxSize);
                } else {
                    waysOfChoosing++;
                    waysOfChoosing += checkHigher(trees, idealAmountOfTrees, i, j, averageSize, minSize, maxSize);
                    waysOfChoosing += checkLower(trees, idealAmountOfTrees, i, j, averageSize, minSize, maxSize);
                }
            }
        }
 
        io.println(waysOfChoosing);
        io.close();
    }
 
    private static int checkHigher(List<MatrixElement> trees, int idealAmountOfTrees,
            int row, int column, int averageSize, int minSize, int maxSize) {
 
        int result = 0;
        int amountOfTrees = trees.size();
        for (int size = averageSize + 1; size < maxSize; size++) {
            int treesInSquare = 0;
            for (int k = 0; k < amountOfTrees; k++) {
                int withinSquare = trees.get(k).withinSquare(column, row, size);
                if (withinSquare == 1) treesInSquare++;
                else if (withinSquare == -1) break;
            }
            if (treesInSquare == idealAmountOfTrees) result++;
            else if (treesInSquare > idealAmountOfTrees) break;
        }
        return result;
    }
 
    private static int checkLower(List<MatrixElement> trees, int idealAmountOfTrees,
            int row, int column, int averageSize, int minSize, int maxSize) {
 
        int result = 0;
        int amountOfTrees = trees.size();
        for (int size = averageSize - 1; size > minSize; size--) {
            int treesInSquare = 0;
            for (int k = 0; k < amountOfTrees; k++) {
                int withinSquare = trees.get(k).withinSquare(column, row, size);
                if (withinSquare == 1) treesInSquare++;
                else if (withinSquare == -1) break;
            }
            if (treesInSquare == idealAmountOfTrees) result++;
            else if (treesInSquare < idealAmountOfTrees) break;
        }
        return result;
    }
}
 
class MatrixElement {
 
    public final int column;
    public final int row;
 
    public MatrixElement(int i, int j) {
        column = i;
        row = j;
    }
 
    public int withinSquare(int i, int j, int sideLength) {
        if (column >= i && row >= j) {
            if (column <= i + sideLength) {
                if (row <= j + sideLength) {
                    return 1;
                }
            } else {
                return -1;
            }
        }
        return 0;
    }
}

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