矩阵前缀和：找到窗口的*最多数量

#include<iostream>
#include <vector>
#include<algorithm>
#include<cmath>
#include <climits>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define ret return
#define str string
#define vt vector
#define vti vector<int>
#define forc(s,e) for(int i=s;i<e;i++)
#define fori(i,s,e) for(int i=s;i<e;i++)
#define umap unordered_map
#define vmp(vec, map) do { for (size_t i = 0; i < vec.size(); ++i) { (map)[vec[i]] = i; }} while(0)
#define smp(container, map)for (const auto& item : container) {(map)[item]++;}
#define fora(v) for(auto a:v)
template<typename T>
using vvt = vector<vector<T>>;
#define foreach2(container) for(auto& row : container){ for(auto element : row) if(true) std::cout << element << " "; std::cout << std::endl;}
const ll N=1e16;

void solve(){
    int n,m;cin>>n>>m;
    vvt<char> v(n,vt<char>(n));
    fori(i,0,n){
        fori(j,0,n){
            cin>>v[i][j];
        }
    }
//构造前缀数组
    vvt<int> pre(n,vt<int>(n,0));
    if(v[0][0]=='*'){
        pre[0][0]=1;
    }
    else{
        pre[0][0]=0;
    }
//先处理第一行第一列
    forc(1,n){
        if(v[0][i]=='*'){
            pre[0][i]=pre[0][i-1]+1;
        }
        else{
            pre[0][i]=pre[0][i-1];
        }
    }
    forc(1,n){
        if(v[i][0]=='*'){
            pre[i][0]=pre[i-1][0]+1;
        }
        else{
            pre[i][0]=pre[i-1][0];
        }
    }
//再处理后面的
    fori(i,1,n){
        fori(j,1,n){
            if(v[i][j]=='*'){
                pre[i][j]=pre[i-1][j]+pre[i][j-1]+1-pre[i-1][j-1];
            }
            else{
                pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
            }
        }
    }
    int ans=INT_MIN;
//枚举所有位置，用O(1)找到每个窗口*的数量，如果直接暴力计算，会在枚举窗口里面的每个字符，会有O(m*m)，这个直接用O(1)计算出了数量
    fori(i,0,n-m+1){
        fori(j,0,n-m+1){
            if(i==0&&j==0){
                ans=max(ans,pre[i+m-1][j+m-1]);//为了保证不越界，分情况讨论，其实也可以直接在开数组时，多1行，1列，让元素从下标1开始，这样就不需要多余的情况判断，直接使用最后一个公式。
            }
            else if(i==0&&j!=0){
                ans=max(ans,pre[i+m-1][j+m-1]-pre[i+m-1][j-1]);
            }
            else if(i!=0&&j==0){
                ans=max(ans,pre[i+m-1][j+m-1]-pre[i-1][j+m-1]);
            }
            else{
                ans=max(ans,pre[i+m-1][j+m-1]-pre[i-1][j+m-1]-pre[i+m-1][j-1]+pre[i-1][j-1]);
            }
        }
    }
    cout<<ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    ret 0;
}