AtCoder Beginner Contest 337 D

nannandbk / 2024-02-01 / 原文

AtCoder Beginner Contest 337 D

D - Cheating Gomoku Narabe

题意：$W$ 列的矩阵，矩阵由 o、x、. 三种字符组成。你可以进行若干次操作（可以不做），每次操作可以把矩阵中的一个 . 改成 o。请问最少经过多少次操作后，能在矩阵中找到位于同一行或同一列的连续 $K$ 个 o。

思路：这题思路挺有意思的，有点滑动窗口的味道。要同一行或同一列有连续$K$个$o$，且只能把$.$变成$o$。我们行和列分开做，做法是一样的，我们以行为例。

我们用$t_1$统计$o$的个数，$t_2$统计连续$o$和$.$的个数

如果当前的是$x$那么$t_1,t_2$置0，因为包含当前这个字符的最大连续是0。

如果当前是$o$,那么$t_1++,t_2++$。

如果当前是$.$的话$t_2++$。

如果$t2>k$的话，说明已经划出去长度为k的了，那么多出去的那个要删掉，如果删掉的那个是$o$那么$t_1$要$--$。

如果$t2\ge k$的话说明可以作为答案，更新答案为$ans = min(ans,k-t_1)$其中$k-t_1表示(需要的o-已有的o)$

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,m,k,t1,t2;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>m>>k;
    char a[n+10][m+10];
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)cin>>a[i][j];
    int ans = 1e9;
    for(int i = 1;i <= n; i++)
    {
        t1 = 0,t2 = 0;
        for(int j = 1;j <= m; j++)
        {
            if(a[i][j]=='x') t1 = t2 = 0;
            else if(a[i][j]=='o')t1++,t2++;
            else t2++;
            if(t2>k&&a[i][j-k]=='o')t1--;
            if(t2>=k)ans = min(ans,k-t1);
        }   
    }
    for(int j = 1;j <= m; j++)
    {
        t1 = 0,t2 = 0;
        for(int i = 1;i <= n; i++)
        {
            if(a[i][j]=='x') t1 = t2 = 0;
            else if(a[i][j]=='o')t1++,t2++;
            else t2++;
            if(t2>k&&a[i-k][j]=='o')t1--;
            if(t2>=k)ans = min(ans,k-t1);
        }   
    }
    cout<<(ans==1e9?-1:ans)<<"\n";
    return 0;
}