#include #include #include #include using namespace std; typedef long long LL; const int N = 2010, INF = 0x3f3f3f3f; LL ans; int h, w, kk, a[N][N], f[2][N][30], num[N]; int main() { // freopen("square.in", "r", stdin); // freopen("square.out", "w", stdout); scanf("%d%d%d", &h, &w, &kk); for (int i = 1; i <= h; ++i) { string s; cin >> s; for (int j = 1; j <= w; ++j) { a[i][j] = s[j - 1] - 'a'; } } memset(f, 0x3f, sizeof(f)); for (int i = h; i >= 1; --i) { for (int j = w; j >= 1; --j) { int cnt = 0; for (int k = 0; k < 26; ++k) { f[i & 1][j][k] = INF; if (a[i][j] == k) f[i & 1][j][k] = 1; f[i & 1][j][k] = min(f[i & 1][j][k], min(f[i & 1 ^ 1][j][k], min(f[i & 1 ^ 1][j + 1][k], f[i & 1][j + 1][k])) + 1); num[++cnt] = f[i & 1][j][k]; } nth_element(num + 1, num + kk, num + cnt + 1); int kth_e = num[kk]; int len = min(h - i + 1, w - j + 1); int up = len + 1; if (kk < 26) { nth_element(num + 1, num + kk + 1, num + cnt + 1); up = min(up, num[kk + 1]); } if (kth_e <= len) ans += up - kth_e; } } printf("%lld\n", ans); return 0; }