本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-25 11:24:42

题目大意：

给你一个矩阵，求出还需要修改多少个点就可以满足有 $K$ 个连续的 $O$ （只能是横向或者纵向）。 其中只可以修改 $·$ ，不能修改 $X$ 。

Solution

首先我们分为两步来进行计算。

横向

对于每一行我们可以用一个队列进行统计，一开始在队列中放入前 $K$ 个元素，然后我们不断向右移动，每一次移动把最头上的出队，最后面的入队，同时我们统计出当前的队列中有多少 $O$ 以及有没有 $X$ 。如果没有 $X$ ，那么就统计所需最少的变化次数。

纵向

方法相同就不再说了。

小细节

$H W$的范围是通过乘积的方式给出，所以我们开数组的时候要动态开，可以有三种选择：

1. 在主函数中根据 $H W$ 的值来开数组

string

vector

CODE

#include<bits\/stdc++.h>
using namespace std;
int ans=0x3f3f3f3f,n,m,k;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	char a[n+5][m+5];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	if(m>=k){
		for(int i=1;i<=n;i++){
			queue<char> q;
			int flag=0,sum=0;
			for(int j=1;j<k;j++){
				if(a[i][j]=='x') flag++;
				if(a[i][j]=='.') sum++;
				q.push(a[i][j]);
			}
			for(int j=k;j<=m;j++){
				q.push(a[i][j]);
				if(a[i][j]=='x') flag++;
				if(a[i][j]=='.') sum++; 
				if(flag==0){
					ans=min(ans,sum);
				}
				if(q.front()=='x') flag--;
				if(q.front()=='.') sum--;
				q.pop();
			}
		}		
	}
	if(n>=k){
		for(int i=1;i<=m;i++){
			queue<char> q;
			int flag=0,sum=0;
			for(int j=1;j<k;j++){
				if(a[j][i]=='x') flag++;
				if(a[j][i]=='.') sum++;
				q.push(a[j][i]);
			}
			for(int j=k;j<=n;j++){
				q.push(a[j][i]);
				if(a[j][i]=='x') flag++;
				if(a[j][i]=='.') sum++; 
				if(flag==0){
					ans=min(ans,sum);
				}
				if(q.front()=='x') flag--;
				if(q.front()=='.') sum--;
				q.pop();
			}
		}		
	}
	if(ans!=0x3f3f3f3f) cout<<ans;
	else cout<<-1;
	return 0;
}