Codeforces 1194B. Yet Another Crosses Problem

传送门

直接枚举填满哪一行，然后看看这一行填满以后哪一列最小

这个预处理一下 $cnt[i]$ 表示初始时第 $i$ 列有几个位置填满就可以做到 $O(m)$

对于所有情况取个 $min$ 就是答案，复杂度 $O(nm)$

存输入用 $string$ 即可，多组数据记得清空

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline 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<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=4e5+7;
const int INF=1e9+7;
int Q,n,m,cnt[N],ans;
string s[N];
int main()
{
    Q=read();
    while(Q--)
    {
        for(int i=1;i<=n;i++) s[i].clear();
        for(int i=0;i<m;i++) cnt[i]=0;
        n=read(),m=read(); ans=INF;
        for(int i=1;i<=n;i++)
        {
            cin>>s[i];
            for(int j=0;j<m;j++) cnt[j]+=s[i][j]=='*';
        }
        for(int i=1;i<=n;i++)
        {
            int tot=0; for(int j=0;j<m;j++) tot+=s[i][j]=='*';
            for(int j=0;j<m;j++) ans=min(ans, m-tot+ n-(cnt[j]+(s[i][j]!='*')) );
        }
        printf("%d
",ans);
    }
    return 0;
}