TopCoder SRM 574, Division 2, Level 2 : TheNumberGameDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12485&rd=15494

概要

数に対して、以下の二つの操作を定義する。

• 数を反転する
• 数を 10 で除し、剰余は切り捨てる

二つの数 A, B が与えられる。
上記の操作で A を B に変換するとき、必要な操作回数の最小値を求めよ。
変換が不可能な場合は -1 で示せ。

解法

最適な変換手順をコードに落とし込んでもよいですが、場合分けの漏れなどが不安です。
この問題の場合、探索空間がさほど広くないので全探索が間に合います。
深く考えずに BFS をしてしまった方が楽でしょう。

コード

typedef istringstream ISS;
typedef ostringstream OSS;

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

#define ALL( c ) (c).begin(), (c).end()

#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

class TheNumberGameDiv2
{
public:
	int minimumMoves( int A, int B )
	{
		string strA( itos( A ) ), strB( itos( B ) );

		queue< pair<int,string> > que;
		que.push( MP( 0, strA ) );

		set<string> visited;
		visited.insert( strA );

		while ( !que.empty() )
		{
			int turn = que.front().fst;
			string str = que.front().snd;
			que.pop();

			if ( str == strB )
			{
				return turn;
			}

			{ // reverse
				string rev( str );
				reverse( ALL( rev ) );
				if ( !EXIST( visited, rev ) )
				{
					que.push( MP( turn + 1, rev ) );
					visited.insert( rev );
				}
			}

			{ // divide
				int n = stoi( str );
				n /= 10;
				string next( itos( n ) );
				if ( !EXIST( visited, next ) )
				{
					que.push( MP( turn + 1, next ) );
					visited.insert( next );
				}
			}
		}

		return -1;
	}

	string itos( int n )
	{
		OSS oss;
		oss << n;
		return oss.str();
	}

	int stoi( string str )
	{
		ISS iss( str );
		int n;
		iss >> n;
		return n;
	}
};