InterviewStreet —— Hanoi Moves

昨日leetcode downを発見したので、別のonline judgeサイトinterviewstreetを探しました.
初めて游んで、感じはとても新鲜で、风格はleetcodeと多く异なって、interviewstreetは时间限定で问题に答えて、とても挑戦します.
また、sample case以外のcaseの内容は非表示になり、結果のみが表示されます.
私が作ったのはsample testで、3つのテーマをあげました.Hanoi Moves  2.ツリーの最長パス3.N以内の素数個数
全部で45分しかかかりませんでしたが、自分のコード能力が悪いので、最初の問題が完成しないうちに時間になりました.ほほほ
よく修練する.全体的に2,3の2つの問題は相対的に水が多いような気がします.第一題について話しましょう.
原題:
Question 1/3 (Hanoi Moves) There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves. A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg. At anypoint of time, the decreasing radius property of all the pegs must be maintained. Constraints: 1<= N<=8 3<= K<=5 Input Format: N K 2nd line contains N integers. Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration. 3rd line denotes the final configuration in a format similar to the initial configuration. Output Format: The first line contains M - The minimal number of moves required to complete the transformation. The following M lines describe a move, by a peg number to pick from and a peg number to place on. If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one. Sample Input #00: 2 3 1 1 2 2 Sample Output #00: 3 1 3 1 2 3 2 Sample Input #01:
6 4 4 2 4 3 1 1 1 1 1 1 1 1 Sample Output #01: 5 3 1 4 3 4 1 2 1 3 1 NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout If you are using "Java", the classname is "Solution"
考え方:テーマを読むのに10分もかかりません.英語は力がありませんね.
実はこの問題は簡単なdfsで、それから簡単な枝を加えます.
C++のSTLに不慣れで、コードを書くスピードに深刻な影響を及ぼして、え~~~
直接コード:

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int minMoveNum;
int N, K;
vector<pair<int, int> > minTraces;
vector<vector<int> > midState;
vector<vector<int> > finalState;

int init() {
    midState.clear();
    finalState.clear();
    for (int i=0; i<K; i++) {
    	vector<int> temp;
        midState.push_back(temp);
        finalState.push_back(temp);
    }
    int peg;
    for (int i = 1; i<=N; i++) {
        cin >> peg;
        midState[peg-1].insert(midState[peg-1].begin(), i);
    }
    for (int i = 1; i<=N; i++) {
        cin >> peg;
        finalState[peg-1].insert(finalState[peg-1].begin(), i);
    }
    minMoveNum = 7;
}

bool doMatch() {
    for (int i=0; i<K; i++) {
        if (midState[i].size() == finalState[i].size()) {
            for (int j=0; j<midState[i].size(); j++)
                if (midState[i][j] != finalState[i][j])
                	return false;
        } else 
			return false;
    }
    return true;
}

bool dfs(vector<pair<int, int> > &traces) {
    if (traces.size() >= minMoveNum)
        return false;
	if (doMatch()) {
		if (traces.size() < minMoveNum) {
			minMoveNum = traces.size();
			minTraces = traces;
		}
		return false;
	}

    for (int i=0; i<K; i++) {
		if (midState[i].size() == 0)
			continue;
		int from = midState[i].back();
		midState[i].pop_back();
        for (int j = (i+1)%K; j != i; j = (j+1)%K) {
			if (midState[j].size()>0 && midState[j].back()<from)
				continue;
			midState[j].push_back(from);
			traces.push_back(pair<int, int>(i+1, j+1));
			if (dfs(traces))
				return true;
			else {
				traces.pop_back();
				midState[j].pop_back();
			}
        }
		midState[i].push_back(from);
    }
	return false;
}

int main() {
	while (cin >> N >> K) {
		init();
		vector<pair<int, int> > traces;
		dfs(traces);
		cout << minMoveNum << endl;
		for (int i=0; i<minMoveNum; i++)
			cout << minTraces[i].first << " " << minTraces[i].second << endl;
	}

	return 0;
}