刚刚abc d题求调
  • 板块题目总版
  • 楼主2c_s
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/20 21:45
  • 上次更新2024/1/21 08:31:53
查看原帖
刚刚abc d题求调
583186
2c_s楼主2024/1/20 21:45

rt,磕了 40 分钟。。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,k,h[N],w[N],a[N],b[N];
//a 记录每行'x'前缀个数
//b 记录每列'x'前缀个数
//h 记录每行'o'前缀个数
//w 记录每列'o'前缀个数
char c[N];
int main(){
	cin>>n>>m>>k;
	for(int i=0;i<n;++i){//处理行
		for(int j=0;j<m;++j){
			cin>>c[i*m+j];
			if(c[i*m+j]=='x'){
				if(j!=0)a[i*m+j]=a[i*m+j-1]+1;
				else if(j==0)a[i*m]=1;
			}
			if(c[i*m+j]=='o'){
				if(j!=0)h[i*m+j]=h[i*m+j-1]+1,a[i*m+j]=a[i*m+j-1];
				else if(j==0)h[i*m]=1;
			}
			if(c[i*m+j]=='.'){
				if(j!=0){
					h[i*m+j]=h[i*m+j-1];
					a[i*m+j]=a[i*m+j-1];
				}
			}
		}
	}
	for(int j=0;j<m;++j){//处理列
		for(int i=0;i<n;++i){
			if(c[i*m+j]=='x'){
				if(i!=0)b[i*m+j]=b[i*m+j-m]+1;
				else if(i==0)b[j]=1;
			}
			if(c[i*m+j]=='o'){
				if(i!=0)w[i*m+j]=w[i*m+j-m]+1,b[i*m+j]=b[i*m+j-m];
				else if(i==0)w[j]=1;
			}
			if(c[i*m+j]=='.'){
				if(i!=0){
					w[i*m+j]=w[i*m+j-m];
					b[i*m+j]=b[i*m+j-m];
				}
			}
		}
	}
	int ans=1e9;
	for(int i=0;i<n;++i){//判断行最小值
		for(int j=k-1;j<m;++j){
			if(a[i*m+j]-a[i*m+j-k]==0)
				ans=min(ans,k-(h[i*m+j]-h[i*m+j-k]));
		}
	}
	for(int j=0;j<m;++j){//判断列最小值
		for(int i=k-1;i<n;++i){
			if(b[i*m+j]-b[i*m+j-k*m]==0)
				ans=min(ans,k-(w[i*m+j]-w[i*m+j-k*m]));
		}
	}
	if(ans==(int)1e9)ans=-1;//如果没有就改成 -1
	cout<<ans;
	return 0;
}
2024/1/20 21:45
加载中...