Question

ABC337 D Cheating Gomoku Narabe

给出一个 \(H\times W\) 的矩阵，由 o，x，. 组成，一次操作为把一个 . 变成 o ，问需要最少多少次操作使得横着或竖着有连续的 \(K\) 个 o

Solution

先来考虑只有一行的情况，我们定义一个长度为 \(K\) 的 "窗口"，假设需要把这个 "窗口" 里面的所有字母都变成 o，将窗口右移，对于每一种情况取一个最小值就是答案

那么，我们如何维护每个窗口里面 x 的数量和 . 的数量，当 x 的数量 \(>0\) 时，说明这个窗口不可能满足条件，. 的数量就表示这个窗口达到满足条件需要操作的次数

定义 num_ 和 num_x 表示当前窗口 x 的数量和 . 的数量，把窗口往右移动的时候，改变的量只有头和尾两个元素，我们只需要判断两个元素是否为 x 和 . 即可

如果多行的情况，对每一行单独处理，然后翻转行和列再处理一次

当然，这题用双指针和前缀和也能做

Code

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

char read_ch(){
    char ch=getchar();
    while(ch!='.'&&ch!='o'&&ch!='x') ch=getchar();
    return ch;
}

int main(){
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    int n = read(), m = read(), k = read();
    vector<vector<int> > a(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j] = read_ch();
    int ans = INF;
    
    if(k <= m)
        for(int i=1;i<=n;i++){
            int num_ = 0,num_x = 0;
            for(int j=1;j<=k;j++){
                if(a[i][j]=='.') num_++;
                if(a[i][j]=='x') num_x++;
            }
            if(num_x==0) ans = min(ans,num_);
            for(int j=k+1;j<=m;j++){
                int t_1 = j-k, t_2 = j;
                if(a[i][t_1]=='.') num_--;
                if(a[i][t_1]=='x') num_x--;
                if(a[i][t_2]=='.') num_++;
                if(a[i][t_2]=='x') num_x++;
                if(num_x==0) ans = min(ans,num_);
            }
        }

    if(k <= n)
        for(int j=1;j<=m;j++){
            int num_ = 0,num_x = 0;
            for(int i=1;i<=k;i++){
                if(a[i][j]=='.') num_++;
                if(a[i][j]=='x') num_x++;
            }
            if(num_x==0) ans = min(ans,num_);
            for(int i=k+1;i<=n;i++){
                int t_1 = i-k, t_2 = i;
                if(a[t_1][j]=='.') num_--;
                if(a[t_1][j]=='x') num_x--;
                if(a[t_2][j]=='.') num_++;
                if(a[t_2][j]=='x') num_x++;
                if(num_x==0) ans = min(ans,num_);
            }
        }

    printf("%d\n",ans == INF ? -1 : ans);
    return 0;
}

双指针

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

char read_ch(){
    char ch=getchar();
    while(ch!='.'&&ch!='o'&&ch!='x') ch=getchar();
    return ch;
}

int main(){
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    int n = read(), m = read(), k = read();
    vector<vector<int> > a(n+5,vector<int>(m+5));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j] = read_ch();
    int ans = INF;
    
    for(int i=1;i<=n;i++){
        int r = 0;
        int now_ans = 0, now_k = 0;
        for(int j=1;j<=m;j++){
            while(r + 1 <= m && now_k < k) {
                if(a[i][r+1] == '.') now_ans++ , now_k++;
                if(a[i][r+1] == 'o') now_k++;
                r++;
            }
            if(now_k >= k && r-j+1 == k) ans = min(ans, now_ans);
            if(a[i][j] == '.') now_ans-- , now_k--;
            if(a[i][j] == 'o') now_k--;
        }
    }

    for(int j=1;j<=m;j++){
        int r = 0;
        int now_ans = 0, now_k = 0;
        for(int i=1;i<=n;i++){
            while(r + 1 <= n && now_k < k) {
                if(a[r+1][j] == '.') now_ans++ , now_k++;
                if(a[r+1][j] == 'o') now_k++;
                r++;                
            }
            if(now_k >= k && r-i+1==k) ans = min(ans, now_ans);
            if(a[i][j] == '.') now_ans-- , now_k--;
            if(a[i][j] == 'o') now_k--;
        }
    }

    printf("%d\n",ans == INF ? -1 : ans);
    return 0;
}