1 条题解

  • 0
    @ 2023-6-21 19:59:14

    C++ :

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    inline void read(int &x){
    	x=0;char ch;bool flag = false;
    	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
    }
    int n;
    namespace work1{
    	const int maxn = 2424;
    	bool map[maxn][maxn];
    	bool can[maxn];
    char   s[maxn];
    	char ch;
    	int a[maxn];
    	int main(){
    		bool flag = false;
    		for(int i=1;i<=n;++i){
    		  scanf("%s",s+1);
    			for(int j=1;j<=n;++j){
    
    				map[i][j] = (s[j] == '#');
    				flag |= map[i][j];
    				if(map[i][j]) ++ a[j];
    			}
    		}
    		if(!flag) return puts("-1");
    		for(int i=1;i<=n;++i){
    			for(int j=1;j<=n;++j){
    				if(map[j][i]){
    					can[i] = true;
    				}
    			}
    		}
    		int nd = 0,cost = 0,ans = 0x7f7f7f7f;
    		for(int i=1;i<=n;++i){
    			nd += (a[i] != n);
    		}
    		for(int i=1;i<=n;++i){
    			cost = 0;
    			bool flag = false;
    			for(int j=1;j<=n;++j){
    				if(map[i][j]) continue;
    				++ cost;
    				flag = true;
    			}
    			if(!can[i] && flag) ++ cost;
    			ans = min(ans,cost+nd);
    		}
    		printf("%d\n",ans);
    		return 0;
    	}
    }
    int main(){
    	read(n);
    	work1::main();
    //	work2::main();
    	return 0;
    }
    
    • 1

    信息

    ID
    1009
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    2
    上传者