torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #192, Division 2, A : Cakeminator

概要

R * C のグリッド状のケーキがあり、いくつかのセルは食べることができない。
一つの行または列を選んで(全て食べられるセルであれば)食べる操作を複数回行える。
食べることのできるセルの数の最大値を求めよ。

解法

食べられる行または列については、全て食べてしまった方がよいということが言えます。
先に行について列挙して、列については高さからすでに食べた数(食べられる行の数)を引いた分を足し込んでいけばよいです。

コード

typedef vector<string> VS;

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

bool okcolum( const VS &board, const int x )
{
	REP( i, 0, board.size() )
	{
		if ( board[i][x] == 'S' )
		{
			return false;
		}
	}
	return true;
}

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

	int h, w;
	cin >> h >> w;

	VS board( h );
	FOR( line, board )
	{
		cin >> line;
	}

	int rows = 0;
	FOR( line, board )
	{
		rows += line == string( w, '.' );
	}

	if ( rows == h )
	{
		cout << h * w << endl;
		return 0;
	}

	int rest = 0;
	REP( ix, 0, w )
	{
		if ( okcolum( board, ix ) )
		{
			rest += h - rows;
		}
	}

	cout << rows * w + rest << endl;

	return 0;
}