用差分数组可以加速,一个长度为n的安全区域中每个区域的m值为f(n,k),但是题目数据量小,直接暴力,数学关系就大咩了。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
void changer(vector<vector<int>>& arr,int i,int j,int jr){
for (int jj=j;jj<=jr;++jj) arr[i][jj]++; //对行区间范围内m值加1
}
void changec(vector<vector<int>>& arr,int j,int i,int id){
for (int ii=i;ii<=id;++ii) arr[ii][j]++;//对列区间范围内m值加1
}
int main(){
int n,k;
cin>>n>>k;
vector<string> sea(n);
string tmp;
for (int i=0;i<n;++i){
cin>>tmp;
sea[i]=tmp;
}
vector<vector<int>> row(n,vector<int>(n,0)),col(n,vector<int>(n,0));//记录m值
for (int i=0;i<n;++i){
for (int j=0;j<n;++j){
if (sea[i][j]=='.') {
int jr=j;
while(jr+1<n && sea[i][jr+1]=='.' && jr-j+1<k) ++jr;//计算行区间m值
if (jr-j+1==k) changer(row,i,j,jr);
int id=i;
while(id+1<n && sea[id+1][j]=='.' && id-i+1<k) ++id;//计算列区间m值
if (id-i+1==k) changec(col,j,i,id);
}
}
}
int r=0,c=0;
int m=0;
for (int i=0;i<n;++i){
for (int j=0;j<n;++j){
if (row[i][j]+col[i][j]>m) {
r=i;
c=j;
m=row[i][j]+col[i][j];//取最大
}
//cout<<"["<<row[i][j]<<","<<col[i][j]<<"]";
}
//cout<<endl;
}
cout<<r+1<<" "<<c+1<<endl;
}