/* -*- 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; /* typedef */ typedef long long ll; /* global variables */ char s[MAX_W + 4]; int css[26][MAX_H + 1][MAX_W + 1]; /* subroutines */ inline int stlb(int i, int j, int maxl, int k) { int l0 = 0, l1 = maxl + 1; while (l0 + 1 < l1) { int l = (l0 + l1) / 2; int num = 0; for (int c = 0; c < 26; c++) if (css[c][i + l][j + l] - css[c][i + l][j] - css[c][i][j + l] + css[c][i][j] > 0) num++; if (num >= k) l1 = l; else l0 = l; } return l1; } /* main */ int main() { int h, w, k; scanf("%d%d%d", &h, &w, &k); for (int i = 0; i < h; i++) { scanf("%s", s); for (int j = 0; j < w; j++) { int cij = s[j] - 'a'; for (int c = 0; c < 26; c++) css[c][i + 1][j + 1] = ((cij == c) ? 1 : 0) + css[c][i + 1][j] + css[c][i][j + 1] - css[c][i][j]; } } ll sum = 0; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) { int maxl = min(h - i, w - j); int l0 = stlb(i, j, maxl, k); if (l0 <= maxl) { int l1 = stlb(i, j, maxl, k + 1); sum += l1 - l0; } } printf("%lld\n", sum); return 0; }