正文

矩阵[雅礼集训 2017 Day1]

IP云
IP云V管理员/0 阅读
09/18
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

SOL 奇奇怪怪的贪心（你也不要问我为什么）

#include<bits/stdc++.h>
#define N 1007
int f[N][N],sum,ans,Ha,bo,n,Ans;
#define MARICLE __attribute__((optimize("-O3")))
char ch,mp[N][N];
using namespace std;
MARICLE void write(int x) {if (x<) {putchar(''+x);return;} write(x/); putchar(''+x%);}
MARICLE inline void writeln(int x) {if (x<) putchar('-'),x*=-; write(x); putchar('\n');}
MARICLE int main () {
//  freopen("a.in","r",stdin);
    scanf("%d\n",&n);
    for (int i=; i<=n; ++i) scanf("%s", mp[i]+);
    for (int i=;i<=n;i++) for (int j=;j<=n;j++) f[i][j]=(mp[i][j]=='#'),sum+=f[i][j];
    Ans=1e9;
    if (!sum) {writeln(-);return ;}
    for (int i=;i<=n;i++) {bo=;
      for (int j=;j<=n;j++) bo&=f[j][i];
      Ha+=-bo;
     }
    for (int i=;i<=n;i++) {
        ans=;bo=;
        for (int j=;j<=n;j++) ans+=f[i][j],bo|=f[j][i];
        ans=n-ans;
        if (!ans) {Ans=;break;}
        Ans=min(ans+-bo,Ans);
    }
    writeln(Ans+Ha);return ;
}