#pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #include #define rep(i, n) for (lli i = 0; i < (n); i++) #define rrep(i, n) for (lli i = (n)-1; i >= 0; i--) using namespace std; using lli = long long int; void YESNO(bool), YesNo(bool); template bool chmin(T1 &l, const T2 &r); template bool chmax(T1 &l, const T2 &r); int c[2005][2005]; int sum[2005][2005][26] = {}; inline int f(int l, int i, int j, int p) { return sum[i + p][j + p][l] - sum[i + p][j][l] - sum[i][j + p][l] + sum[i][j][l]; } int h, w, k; int calc(int i, int j, int p) { // [up, n)でp種類以上 int up1 = min(h - i, w - j) + 1; int low1 = 0; const int h = h; const int w = w; const int k = k; while (up1 - low1 > 1) { int mid = (up1 + low1) / 2; int cnt = 0; rep(l, 26) cnt += (f(l, i, j, mid) >= 1); (cnt >= p ? up1 : low1) = mid; } if (up1 == 0) return 0; int up2 = up1; int low2 = 0; p--; while (up2 - low2 > 1) { int mid = (up2 + low2) / 2; int cnt = 0; rep(l, 26) cnt += (f(l, i, j, mid) >= 1); (cnt >= p ? up2 : low2) = mid; } return up1 - up2; } int main() { cin >> h >> w >> k; rep(i, h) rep(j, w) { char ch; cin >> ch; c[i][j] = ch - 'a'; } rep(i, h) rep(j, w) rep(l, 26) sum[i + 1][j + 1][l] = sum[i][j + 1][l] + sum[i + 1][j][l] - sum[i][j][l] + int(c[i][j] == l); lli ret = 0; rep(i, h) rep(j, w) { // cout << i << " " << j << " " << calc(i, j, k) << endl; // cout << i << " " << j << " " << calc(i, j, k + 1) << endl; ret += calc(i, j, k + 1); } cout << ret << endl; } // -- lib void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; } void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; } template bool chmin(T1 &l, const T2 &r) { return (l > r) ? (l = r, true) : false; } template bool chmax(T1 &l, const T2 &r) { return (l < r) ? (l = r, true) : false; }