#include #include // #include using namespace std; typedef unsigned CHARSET; const CHARSET ALLCHARS = 0x3FFF; inline CHARSET setChar(CHARSET org, char chr) { return (org | (0x01 << (chr - 'a'))); } //! return -1 when the number of bits set in cs < val //! return 0 when the number of bits set in cs == val //! return +1 when the number of bits set in cs > val inline int check(CHARSET cs, int val) { if (cs == ALLCHARS) { return (val == 26 ? 0 : 1); } int cnt = 0; for (unsigned i = 0, m = 0x01; i < 26; ++i, m <<= 1) { if ((m & cs) != 0) { ++cnt; if (val < cnt) { return 1; } } } return (val == cnt ? 0 : -1); } int main() { int H, W, K; cin >> H >> W >> K; vector c(H*W); for (int y = 0; y < H; ++y) { for (int x = 0; x < W; ++x) { cin >> c[W * y + x]; } } int minLen = 1; //! min length of a side of the square with level K while (minLen * minLen < K) { ++minLen; } int maxLen = min(H, W); //! max length of a side of the square int ans = 0; vector charSets(H*W); //! charSets[W * y + x] contains the CHARSET for the square with top left corner on (x, y) for (int y = 0; y < H - minLen + 1; ++y) { for (int x = 0; x < W - minLen + 1; ++x) { CHARSET& s = charSets[W * y + x]; for (int oy = 0; oy < minLen; ++oy) { for (int ox = 0; ox < minLen; ++ox) { s = setChar(s, c[W * (y + oy) + x + ox]); } } int ck = check(s, K); if (ck == 0) { ++ans; } else if (0 < ck) { s = ALLCHARS; } } } for (int len = minLen+1; len <= maxLen; ++len) { vector nextCharSets(H*W); for (int y = 0; y < H - len + 1; ++y) { for (int x = 0; x < W - len + 1; ++x) { CHARSET& s = nextCharSets[W * y + x]; s = charSets[W * y + x] | charSets[W * (y+1) + x] | charSets[W * y + x+1] | charSets[W * (y+1) + x+1]; int ck = check(s, K); if (ck == 0) { ++ans; } else if (0 < ck) { s = ALLCHARS; } } } charSets.swap(nextCharSets); } cout << ans << endl; return 0; }