TopCoder SRM 618 Div2 Hard MovingRooksDiv2

問題設定が妙にややこしいが、中身の問題自体はシンプル。
http://community.topcoder.com/stat?c=problem_statement&pm=13065

問題

問題文はチェスのルークがどうこうと書かれているが、シンプルに書くとこうなる。

0～(N-1)のpermutationの形をした数列が与えられる。
数列の２要素について、後ろの要素の方が大きい場合、両者をスワップ可能である。
数列の初期状態と終了状態を与えられたとき、上記スワップ処理で遷移可能か答えよ。

解法

N<=8なので状態数はさほど多くない。
遷移可能な状態を全列挙しても間に合う。

class MovingRooksDiv2 {
	public:
	string move(vector <int> Y1, vector <int> Y2) {
		int N=Y1.size();
		int x,y;
		
		set<vector<int> > S, S2;
		S.insert(Y1);
		S2.insert(Y1);
		while(!S2.empty()) {
			vector<int> W=*S2.begin();
			S2.erase(S2.begin());
			if(equal(W.begin(),W.end(),Y2.begin())) return "Possible";
			
			FOR(x,N) for(y=x+1;y<N;y++) if(W[x]>W[y]) {
				swap(W[x],W[y]);
				if(S.find(W)==S.end()) S.insert(W),S2.insert(W);
				swap(W[x],W[y]);
			}
		}
		return "Impossible";
		
	}
};

まとめ

なんか今回Div2 MediumもDiv2 Hardもやるだけ問題だな…。