TopCoder SRM 590, Division 1, Level 1 : FoxAndChess

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12725&rd=15702

概要

セルが一行に並んだ盤面上でゲームをする。
ゲームには二種類の駒を使い、一つは一回の移動で右に一つ移動できる。
他方は一回の移動で左に一つ移動できる。
一つのセルには高々一つの駒のみが存在でき、既に駒のあるセルには移動できない。

盤面状態を表す二つの文字列 begin, target が与えられる。
何回かの操作で begin が表す状態から target が表す状態を作れるかどうか判定せよ。

解法

まず、両文字列から '.' を除いたものが一致しないとき、Impossible になります。
さらに、'.' 以外について考慮したとき、begin の 'L' に対応する target の 'L' の位置が求まります。
その位置が begin のそれより右にあるとき、Impossible です。
'R' についても同様に、begin の 'R' に対応する target の 'R' が左にあれば Impossible です。
これらの条件に当てはまらないとき、Possible です。

コード

#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()

const string res_ok = "Possible";
const string res_ng = "Impossible";

class FoxAndChess
{
public:
	string ableToMove( string begin, string target )
	{
		const int L = begin.size();

		int i, j;
		for ( i = 0, j = 0; ; i++, j++ )
		{
			for ( ; i < L && begin[i] == '.'; i++ );
			for ( ; j < L && target[j] == '.'; j++ );

			if ( max( i, j ) == L )
			{
				break;
			}

			if ( begin[i] != target[j] ||
				 begin[i] == 'L' && i < j ||
				 begin[i] == 'R' && j < i )
			{
				return res_ng;
			}	
		}

		return i == j ? res_ok : res_ng;
	}
}