AT_abc337_d 题解
zibenlun
·
·
题解
题目大意：
给你一个矩阵，求出还需要修改多少个点就可以满足有 K 个连续的 O （只能是横向或者纵向）。
其中只可以修改 · ，不能修改 X 。
Solution
首先我们分为两步来进行计算。
横向
对于每一行我们可以用一个队列进行统计，一开始在队列中放入前 K 个元素，然后我们不断向右移动，每一次移动把最头上的出队，最后面的入队，同时我们统计出当前的队列中有多少 O 以及有没有 X 。如果没有 X ，那么就统计所需最少的变化次数。
纵向
方法相同就不再说了。
小细节
1.
在主函数中根据 $H W$ 的值来开数组
2.
```cpp
string
```
3.
```cpp
vector
```
# CODE
```cpp
#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;
}
```