#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using Pll = pair; using Pii = pair; constexpr ll MOD = 1000000007; constexpr long double EPS = 1e-10; constexpr int dyx[4][2] = { { 0, 1}, {-1, 0}, {0,-1}, {1, 0} }; int h,w,k; int counts[26][2001][2001]; int count_level(int i, int j, int r) { int level = 0; for(int k=0;k<26;++k) { if(counts[k][i+r-1][j+r-1] - counts[k][i+r-1][j-1] - counts[k][i-1][j+r-1] + counts[k][i-1][j-1] > 0) { ++level; if(level > k) break; } } return level; } int binary_search(int i, int j, int k) { int ok = 0, ng = min(h, w); // ok: 半径 ok のとき level <= k; // ng: 半径 ng のとき level > k; while(ng-ok > 1) { int r = (ok+ng) / 2; if(i+r-1 > h || j+r-1 > w) { ng = r; continue; } int level = count_level(i, j, r); if(level > k) { ng = r; } else { ok = r; } } return ok; } int main() { std::ios::sync_with_stdio(false); cin.tie(0); cin >> h >> w >> k; string s; for(int i=1;i<=h;++i) { cin >> s; for(int j=1;j<=w;++j) { for(int k=0;k<26;++k) { counts[k][i][j] = counts[k][i-1][j] + counts[k][i][j-1] - counts[k][i-1][j-1]; } ++counts[int(s[j-1] - 'a')][i][j]; } } int ans = 0; for(int i=1;i<=h;++i) { for(int j=1;j<=w;++j) { int max_r_k = binary_search(i, j, k); int max_r_k1 = binary_search(i, j, k-1); ans += max(0, max_r_k-max_r_k1); // cerr << i << "," << j << ": " << max_r_k << " " << max_r_k1 << endl; } } cout << ans << endl; }