TopCoder, SRM 618, Division 2, Level 3 : MovingRooksDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13065&rd=15851

問題概要

　 のグリッド状の盤面に、n 個の石が置かれている。また、盤面の各行・各列について、そこに置かれている石は丁度一つである。
　この盤面上 ( r1, c1 ), ( r2, c2 ) に置かれている二つの石について、r1 < r2 かつ c1 > c2 を満たすならば、それぞれの石の位置を ( r1, c2 ), ( r2, c1 ) に移動する操作を任意回できる。
　二つの盤面 Y1, Y2 が与えられる。上記の操作を繰り返すことで Y1 から Y2 を作ることができるか否か、求めよ。

解法

　問題文にあるように、盤面に対して操作を施しても、「各行・各列にある石は一つ」という条件は満たされます。従って、各行について石が存在する列の番号を一つずつとってきて並べることができて、これはサイズ n の置換になります。このことから、盤面が取り得る状態の総数は であると分かります。制約より n の最大値は 8 で、8! = 40,320 です。状態数が十分に小さいので、初期状態から遷移可能な状態を全て列挙することができます。従って、Y1 から DFS をして遷移できる状態を列挙し、そこに Y2 が含まれるかどうかをチェックすることで問題を解くことができます。

コード

using VI = vector<int>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

class MovingRooksDiv2
{
public:
	set<VI> visited;
	
	string move(vector <int> Y1, vector <int> Y2)
	{
		visited.clear();

		dfs( Y1 );
		return EXIST( visited, Y2 ) ? "Possible" : "Impossible";
	}

	void dfs( VI &Y )
	{
		if ( EXIST( visited, Y ) )
		{
			return;
		}

		visited.insert( Y );

		const int N = Y.size();

		REP( i, 0, N )
		{
			REP( j, i + 1, N )
			{
				if ( Y[i] > Y[j] )
				{
					swap( Y[i], Y[j] );
					dfs( Y );
					swap( Y[i], Y[j] );
				}
			}
		}

		return;
	}
};