马蜂良好深夜求调(玄两关)
查看原帖
马蜂良好深夜求调(玄两关)
1198296
封禁用户楼主2024/1/25 23:02

rt.

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m,k;
	cin>>n>>m>>k;
	char c[n+5][m+5];
	int r1[n+5][m+5],r2[n+5][m+5],c1[n][m],c2[n][m];//前缀和 
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>c[i][j];
		}for(int j=1;j<=m;++j){
			r1[i][j]=r1[i][j-1]+(c[i][j]=='.');
		}for(int j=1;j<=m;++j){
			r2[i][j]=r2[i][j-1]+(c[i][j]=='x');
		}
	}for(int j=1;j<=m;++j){
		for(int i=1;i<=n;++i){
			c1[i][j]=c1[i-1][j]+(c[i][j]=='.');
		}for(int i=1;i<=n;++i){
			c2[i][j]=c2[i-1][j]+(c[i][j]=='x');
		}
	}int ans=1e18;
	for(int i=1;i<=n;++i){//枚举左端点 
		for(int j=1;j<=m;++j){//枚举上端点 
			int y=j+k-1;//右端点 
			if(y<=m&&r2[i][y]-r2[i][j-1]==0){
				ans=min(ans,r1[i][y]-r1[i][j-1]);
			}int x=i+k-1;
			if(x<=n&&c2[x][j]-c2[i-1][j]==0){
				ans=min(ans,c1[x][j]-c1[i-1][j]);
			}
		}
	}if(ans==1e18) ans=-1;
	cout<<ans<<endl;
	return 0;
}

样例#4过不去

2024/1/25 23:02
加载中...