概要
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; }