Codeforces #192, Division 2, C ( Division 1, A ) : Purification

問題文

http://codeforces.com/contest/330/problem/C

概要

N * N のグリッド状の盤面があり、各セルは '.' または 'E' である。
'.' のセルを一つ選択することで、同じ行・列のセルを全て選択状態にできる。（ 'E' のセルは直接的には選択できない）
全てのセルを選択状態にするために必要な最小手数を求め、選択するセルを全て出力せよ。
そのような手順が存在しない場合は -1 で示せ。

解法

一つのセルを選択することで、行と列をそれぞれ一つずつ埋めることができます。
二つ以上の行または列を埋めることはできないことから、最小手数は N であることが分かります。
N 手は確実に使えるので、行または列について一つずつ選択していくことで全体を選択状態にできます。
ただし、全て 'E' であるような行が存在する場合、行基準にすると解けないが列基準では解けるので両方やります。
同じ理由から、全てが 'E' の列と行がそれぞれ一つ以上存在する場合は解がありません。

コード

typedef vector<string> VS;
typedef pair<int,int> PII;
typedef vector<PII> VPII;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

VPII solve( const VS &board, const bool rot )
{
	const int N = board.size();

	VPII res;
	REP( i, 0, N )
	{
		bool found = false;
		REP( j, 0, N )
		{
			if ( board[i][j] == '.' )
			{
				res.PB( !rot ? MP( i, j ) : MP( j, i ) );
				found = true;
				break;
			}
		}
		if ( !found )
		{
			return VPII( 200 );
		}
	}
	return res;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VS board( n );
	FOR( line, board )
	{
		cin >> line;
	}
	VS rot = [&](){
		VS res( n );
		REP( ix, 0, n )
		{
			REP( iy, 0, n )
			{
				res[ix].PB( board[iy][ix] );
			}
		}
		return res;
	}();

	VPII res = min( solve( board, false ), solve( rot, true ), []( const VPII &a, const VPII &b ){ return a.size() < b.size(); } );
	
	if ( res.size() == 200 )
	{
		cout << -1 << endl;
		return 0;
	}

	FOR( p, res )
	{
		cout << p.fst + 1 << ' ' << p.snd + 1 << endl;
	}

	return 0;
}