#include #include #include #include using namespace std; int main() { int H, W, K; cin >> H >> W >> K; vector> A(H, vector(W)); for (int h = 0; h < H; ++h) { string row; cin >> row; for (int w = 0; w < W; ++w) { A[h][w] = row[w] - 'a'; } } const int inf = 1<<30; vector dp(26 * W, inf); long long ans = 0; for (int h = 0; h < H; ++h) { vector prev = dp; fill(dp.begin(), dp.end(), inf); for (int w = 0; w < W; ++w) { for (int a = 0; a < 26; ++a) { if (A[h][w] == a) { dp[a * W + w] = 0; } if (h > 0) { dp[a * W + w] = min(dp[a * W + w], prev[a * W + w] + 1); } if (w > 0) { dp[a * W + w] = min(dp[a * W + w], dp[a * W + w - 1] + 1); } if (h > 0 && w > 0) { dp[a * W + w] = min(dp[a * W + w], prev[a * W + w - 1] + 1); } } vector idx; for (int a = 0; a < 26; ++a) { if (dp[a * W + w] <= min(h, w)) { idx.push_back(dp[a * W + w]); } } idx.push_back(min(h, w) + 1); if (idx.size() > K) { sort(idx.begin(), idx.end()); ans += idx[K] - idx[K - 1]; } } } cout << ans << endl; return 0; }