/* -*- coding: utf-8 -*- * * 866.cc: No.866 レベルKの正方形 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_H = 2000; const int MAX_W = 2000; const int INF = 1 << 29; /* typedef */ typedef long long ll; /* global variables */ char flds[MAX_H][MAX_W + 4]; int dp[MAX_H + 1][MAX_W + 1][26]; /* subroutines */ inline int min3(int a, int b, int c) { if (a < b) return (a < c) ? a : c; return (b < c) ? b : c; } /* main */ int main() { int h, w, k; scanf("%d%d%d", &h, &w, &k); for (int i = 0; i < h; i++) scanf("%s", flds[i]); for (int i = h; i >= 0; i--) for (int j = w; j >= 0; j--) { if (i == h || j == w) fill(dp[i][j], dp[i][j] + 26, INF); else { int cij = flds[i][j] - 'a'; for (int c = 0; c < 26; c++) { if (c == cij) dp[i][j][c] = 1; else dp[i][j][c] = min3(dp[i][j + 1][c], dp[i + 1][j][c], dp[i + 1][j + 1][c]) + 1; } } } ll sum = 0; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) { int *as = dp[i][j]; sort(as, as + 26); int maxl = min(h - i, w - j); int a0 = as[k - 1]; if (a0 <= maxl) { int a1 = min(maxl + 1, (k >= 26) ? INF : as[k]); sum += a1 - a0; } } printf("%lld\n", sum); return 0; }