Tontti

public class Tontti {
    public static void main(String[] args) {
        IO io = new IO();
        
        int n = io.nextInt();
        int m = io.nextInt();
        int x = io.nextInt();
        
        boolean[][] in = new boolean[n][m];
        int out = 0;
        
        int tr = 0;
        for (int i=0; i<n; i++) {
            String s = io.next();
            for (int j=0; j<m; j++) {
                if (s.charAt(j) == '.') {
                    in[i][j] = false;
                } else {
                    in[i][j] = true;
                    tr++;
                }
            }
        }
        
        int sMin = Math.max(1,(int)Math.ceil(Math.sqrt(x)));
        for (int i=0; i <= n-sMin; i++) {
            for (int j=0; j <= m-sMin; j++) {
                int trees = 0;
                for (int s = sMin; s <= n-i && s <= m-j; s++) {
                    trees = treeCount(in, i, j, s, trees);
                    if (trees == x) {
                        out++;
                    } else if (trees > x) {
                        break;
                    }
                }
            }
        }
        
        io.println(out);
        
        io.close();
    }
    
    private static int treeCount(boolean[][] t, int x, int y, int s, int old) {
//      00000  
//      0xxx0
//      0xxx0
//      0xxx0
//      00000
        int count = old;
        if (old == 0) {
            for (int i=x; i<x+s; i++) {
                for (int j=y; j<y+s; j++) {
                    if (t[i][j]) count++;
                }
            }
        } else {
            for (int i=y; i<y+s; i++) {
                if (t[x+s-1][i]) count++;
            }
            for (int i=x; i<x+s-1; i++) {
                if (t[i][y+s-1]) count++;
            }
        }
        return count;
    }
    
}

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