TopCoder SRM 611, Division 2, Level 3 : ElephantDrinkingEasy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13039&rd=15844

問題概要

　 のフィールドがあり、それぞれのグリッドは水があるか何もないかのいずれかである。フィールドの外部に象がいて、鼻を伸ばして水を飲もうとします。象は鼻をいずれかの座標軸に平行な方向へいくらでも伸ばすことができるが、他の象の鼻が存在するグリッドへは伸ばすことはできない。 象の鼻の先端が水のあるグリッドに到達したとき、その象は水を飲むことができる。最大で何匹の象が水を飲むことができるか、求めよ。
　なお、2 ≦ N ≦ 5 である。

解法

　象が存在しうる場所はフィールド外部であり、フィールドに向かって縦に二匹以上存在しても後ろの象は絶対に水を飲めないので、最大でも 2 * 5 = 20 箇所からしか水を飲めません。この数であれば、それぞれの場所に象を配置するか否かを全て試すことができます。
　象の配置が決まったとき、それぞれの象は一番近い水場から水を飲んだ方が他の象の邪魔をしないので全体で得になります。そのような状態をシミュレートして valid となるか（二本以上の鼻があるセルが存在せず、全ての象が水を飲むことができる）を調べれば、その配置の妥当性を検証できます。妥当な配置の内、最も象が多かったものが問題の答えとなる配置です。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

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

#define PB( n ) push_back( n )

bool inside( const int y, const int x, const int N )
{
	return 0 <= y && y < N && 0 <= x && x < N;
}

struct Elephant
{
	int y, x, d;

	Elephant( int y, int x, int d ) : y( y ), x( x ), d( d ) {};
};

const int dy[] = { 1, 0, -1, 0 };
const int dx[] = { 0, 1, 0, -1 };

class ElephantDrinkingEasy
{
public:
	int maxElephants( vector <string> map )
	{
		const int N = map.size();

		vector<Elephant> es;
		REP( i, 0, N )
		{
			es.emplace_back( 0, i, 0 );
			es.emplace_back( i, 0, 1 );
			es.emplace_back( N - 1, i, 2 );
			es.emplace_back( i, N - 1, 3 );
		}

		const int M = es.size();

		int res = 0;
		REP( s, 1, 1 << M )
		{
			vector<Elephant> es2;
			REP( i, 0, M )
			{
				if ( s & 1 << i )
				{
					es2.PB( es[i] );
				}
			}

			VVI counts( N, VI( N ) );
			int count = 0;
			FOR( e, es2 )
			{
				for ( ; inside( e.y, e.x, N ); e.y += dy[ e.d ], e.x += dx[ e.d ] )
				{
					counts[ e.y ][ e.x ]++;
					if ( map[ e.y ][ e.x ] == 'Y' )
					{
						count++;
						break;
					}
				}
			}

			bool ok = true;
			FOR( line, counts )
			{
				ok &= *max_element( ALL( line ) ) <= 1;
			}

			if ( ok && count == (int)es2.size() )
			{
				res = max<int>( res, es2.size() );
			}
		}
		return res;
	}
};