Submission #1729177

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

char a[501][501];
int n; 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	bool allempty = 1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='#') allempty=0;
		}
	}
	if(allempty)
	{
		cout<<-1<<'\n';
		return 0;
	}
	int fullcol = 0;
	for(int j = 0; j < n; j++)
	{
		bool full=1;
		for(int i=0;i<n;i++)
		{
			if(a[i][j]=='.')
			{
				full=0;
				break;
			}
		}
		if(full) fullcol++;
	}
	if(fullcol==n)
	{
		cout<<0<<'\n'; return 0;
	}
	int minans = 1000000;
	for(int i = 0; i < n; i++)
	{
		//find min steps to make row i full
		int cntemp = 0;
		for(int j = 0; j < n; j++)
		{
			if(a[i][j]=='.') cntemp++;
		}
		if(cntemp==0)
		{
			minans=0; break;
		}
		bool pos=0;
		for(int j = 0; j < n; j++)
		{
			if(a[j][i]=='#')
			{
				pos=1;
			}
		}	
		if(!pos)
		{
			cntemp++;
			pos=1;
		}
		if(pos)
		{
			minans=min(minans,cntemp);
		}
	}
	minans+=n-fullcol;
	cout<<minans<<'\n';
}

Submission Info

Judge Result