分析

由于没有修改操作,所以可以求出二维前缀和,从而达到 判断。二分边长,对每个节点单独考虑就好了,总的时间复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e2+100;
int n,m,K;
int t[N][N][26],sum[N][N][26];
bool check(int x,int y,int D){
    for(int i = 0;i < 26;i++) {
        if(sum[x+D][y+D][i]-sum[x+D][y-1][i]-sum[x-1][y+D][i]+sum[x-1][y-1][i] > K) return false;
    }
    return true;
}
int main()
{
    cin >> n >> m >> K;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            char ch;cin >> ch;
            t[i][j][ch-'a']++;
        }
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            for(int k = 0;k < 26;k++){
                sum[i][j][k] = sum[i-1][j][k] + sum[i][j-1][k] - sum[i-1][j-1][k] + t[i][j][k];
            }
        }
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            int l = 1,ans = 0,r = min(m-j+1,n-i+1);
            while(l <= r) {
                int mid = l + r >> 1;
                if(check(i,j,mid-1)) {
                    ans = max(ans,mid);l = mid + 1;
                }
                else r = mid - 1;
            }
            cout << ans << " ";
        }
        cout << endl;
    }
}