Link

CF1900 A Cover in Water

Question

给出一个 \(n\) 个格子，有些格子被堵塞了，有些格子是空的，我需要在进行一些操作，使得所有空的格子里面都有水

• 操作 1：给任意一个格子装上水
• 操作 2：把一格水从一个地方搬运到另外一个空的格子里

如果一个空的格子的相邻的两个格子都有水，那么这个格子也有水

求把所有格子里面都有水进行的最少操作 1 次数

Solution

如果是 #.# 中间空一个，就只能放一格水，操作 1 次数一次

如果是 #..# 中间空两个，就只能放两格水，操作 1 次数两次

如果是 #...# 中间空大于两个，可以中间空一个放两格水，中间就相当于生成了一个无限生成水的格子，用操作二把这个格子生成的水搬运到别的地方，答案就是二

如果不存在中间空大于两个的格子，就只能一格一格用操作一放水

Code

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

int a[105];
void solve(){
    int N=read(),ans=0;
    for(int i=1;i<=N;i++){
        char ch=getchar();
        while(ch!='.'&&ch!='#') ch=getchar();
        a[i]=(ch=='#');
    }
    a[0]=1;a[N+1]=1;
    for(int i=0;i<=N+1;i++){
        if(a[i]) continue;
        int j=i;
        while(j<=N+1&&a[j]==0) j++;
        if(j-i==1) ans+=1;
        else if(j-i==2)ans+=2;
        else {
            printf("%d\n",2);
            return ;
        }
        i=j;
    }
    printf("%d\n",ans);
    return ;
}
int main(){
    // freopen("A.in","r",stdin);
    int T=read();
    while(T--) solve();
}