#include #include #include #include using namespace std; int wanted; vector>> c_sum; int bin_lower(int x, int y, int max_size) { int ng = 0; int ok = max_size + 1; while (abs(ok - ng) > 1) { int mid = ng + (ok - ng) / 2; int count = 0; for (int i = 0; i < 26; i++) { if (c_sum[x + mid][y + mid][i] - c_sum[x + mid][y][i] - c_sum[x][y + mid][i] + c_sum[x][y][i] > 0)count++; } if (count >= wanted)ok = mid; else ng = mid; } return ok; } int bin_upper(int x, int y, int max_size) { int ng = 0; int ok = max_size + 1; while (abs(ok - ng) > 1) { int mid = ng + (ok - ng) / 2; int count = 0; for (int i = 0; i < 26; i++) { if (c_sum[x + mid][y + mid][i] - c_sum[x + mid][y][i] - c_sum[x][y + mid][i] + c_sum[x][y][i] > 0)count++; } if (count > wanted)ok = mid; else ng = mid; } return ok; } int main() { int h, w; cin >> h >> w >> wanted; vector ban(h); for (int i = 0; i < h; i++)cin >> ban[i]; c_sum = vector>>(h + 1, vector>(w + 1, vector(26))); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { for (int c = 0; c < 26; c++) { c_sum[i + 1][j + 1][c] = c_sum[i + 1][j][c] + c_sum[i][j + 1][c] - c_sum[i][j][c] + (ban[i][j] - 'a' == c ? 1 : 0); } } } int ret = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { int max_size = min(h - i, w - j); int x = bin_upper(i, j, max_size); int y = bin_lower(i, j, max_size); ret += x - y; } } cout << ret << endl; return 0; }