2013 TCO Algorithm - Round 1B, Level 2 : EllysFigurines

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12447

概要

グリッド状の平面にいくつかの人形が置かれている。
一回の操作で、R 個以下の連続する行または C 個以下の連続する列から人形を取り除くことができる。
全ての人形を取り除くのに必要な手数の最小数を求めよ。

解法

まず、消す行を全探索で仮定します。
消す行が決まると残った盤面から消すべき列が決まります。
対象が決まったとき、端から最大幅で消していけば最小手数で消すことができるので、行・列についてこれらを求めた和の最小値が答えになります。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class EllysFigurines
{
public:
	int getMoves( vector <string> board, int R, int C )
	{
		const int H = board.size(), W = board[0].size();
		
		int res = INT_MAX;

		REP( i, 0, 1 << H )
		{
			string rows = string( H, '.' ), cols = string( W, '.' );

			REP( j, 0, H )
			{
				if ( i & ( 1 << j ) )
				{
					rows[j] = 'X';
				}
				else
				{
					REP( k, 0, W )
					{
						if ( board[j][k] == 'X' )
						{
							cols[k] = 'X';
						}
					}
				}
			}


			int tmp1 = check( rows, R ), tmp2 = check( cols, C );
			res = min( res, tmp1 + tmp2 );
		}

		return res;
	}

	int check( string str, int width )
	{
		int res = 0;

		REP( i, 0, str.size() )
		{
			if ( str[i] == 'X' )
			{
				res++;
				for ( int j = 0; j < width && i + j < str.size(); j++ )	
				{
					str[ i + j ] = '.';
				}
			}
		}

		return res;
	}
};