AOJ 0503 - Cup

カップたちの状態をトレース(辿っていく)するだけでも時間に間に合う．
最初，出会った状態に印をつけてましたが，MLE．(じゃなくてもTLE)
そういえば，前回移動したものを戻しちゃ意味ないよなあ．これで状態に重複なくなると思いました．
そしたら，うまく行きました．(2.5sかかりましたが)
もう少し考えたら，B->Aに移動させたら，A->Bは勿論B->Aは移動できない，よってB->CかC->B．
この2つの大小関係は一意に定まる．だからできるっぽい．

辿る解法．

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

typedef long long ll;

struct Cups{
	std::vector<int> S[3];
	int t, prev_from, prev_to;
	Cups(const std::vector<int> (&_S)[3], int _t, int _from, int _to)
		:t(_t), prev_from(_from), prev_to(_to)
	{
		for(int i=0;i<3;i++){
			S[i] = _S[i];
		}
	}
};

int main(){
	int n, m;
	while(std::cin >> n >> m, n){
		std::vector<int> S[3];
		for(int i=0;i<3;i++){
			int SN;
			std::cin >> SN;
			for(int j=0;j<SN;j++){
				int e;
				std::cin >> e;
				S[i].push_back(e-1);
			}
			std::sort(S[i].begin(), S[i].end(), std::greater<int>());
		}

		std::queue<Cups> q;
		q.push(Cups(S, 0, -1, -1));
	
		int res = -1;
		while(!q.empty()){
			Cups c = q.front();q.pop();
			std::vector<int> S[3] = c.S;
			int t = c.t, prev_from = c.prev_from, prev_to = c.prev_to;

			if(t > m){
				continue;
			}
			if(S[0].size() == n || S[2].size() == n){
				res = t;
				break;
			}

			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){//i -> j
					if(std::abs(i-j) != 1 || (j == prev_from && i == prev_to) ||
						 S[i].empty() || (!S[j].empty() && S[i][0] < S[j][0]))continue;
					std::vector<int> _S[3] = S;
					_S[j].push_back(_S[i][0]);
					_S[i].erase(_S[i].begin());
					std::sort(_S[j].begin(), _S[j].end(), std::greater<int>());
					q.push(Cups(_S, t+1, i, j));
				}
			}
		}

		std::cout << res << std::endl;
	}
}

後々，色々読みました．
参考: 公式の解説(ちょーわかりやすい)
AOJ 0503: Cup - Particle(とっても簡潔．すごい．)