Submission #1131975

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef long long lint;
const int mod = 1e9 + 7;

int n;
char a[505][505];

int main(){
	cin >> n;
	bool ok = 0;
	for(int i=0; i<n; i++){
		cin >> a[i];
		if(count(a[i], a[i] + n, '#') > 0) ok = 1;
	}
	if(!ok){
		puts("-1");
		return 0;
	}
	int dap = 0;
			for(int j=0; j<n; j++){
				for(int k=0; k<n; k++){
					if(a[k][j] == '.'){
						dap++;
						break;
					}
				}
			}

	int ans = 1e9;
	for(int i=0; i<n; i++){
		if(count(a[i], a[i] + n, '#') == n){
			ans = min(ans, dap); 
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(a[j][i] == '#'){
				bool ok = (i != j);
				int tmp = 0;
				for(int k=0; k<n; k++){
					if(a[i][k] == '#' && a[j][k] == '.'){
						ok = 0;
					}
					if(a[i][k] == '.') tmp++;
				}
				if(ok){
					ans = min(ans, dap + tmp - 1);
				}
				else{
					ans = min(ans, dap + tmp);
				}
			//	printf("%d %d %d\n", i, j, ans);
			}
		}
	}
	if(ans > 1e8) ans = -1;
	cout << ans << endl;
}

Submission Info

Judge Result