2015年西北工业大学机试第六题

 思路：

可以看作一棵二叉树，两种变化情况看做左右子树，然后查找是否存在某个节点为“123456”，输出最少步数，用BFS，广度优先搜索

#include<stdio.h>
#include<string>
#include<queue>
#include<map>
using namespace std;
string alpha(string s) {
	string result = "";
	return result+s[3]+s[0]+s[2]+s[4]+s[1]+s[5];
}
string beta(string s) {
	string result = "";
	return result+s[0]+s[4]+s[1]+s[3]+s[5]+s[2];
}
struct node{
	string s;
	int step;
	node(string s, int step):s(s), step(step) {}
};
int main() {
	
	int i, n, a, result;
	for (scanf("%d", &n); n--; ) {
		result = -1;
		string input = "";
		for(i = 0; i < 6; scanf("%d", &a), input += '0'+a, i++);
		queue<node> q;
		map<string, int> book;
		for (q.push(node(input, 0)), book[input] = 1; !q.empty(); ) {
			node head = q.front(); q.pop();
			printf("%s\n", head.s.c_str());
			if (head.s == "123456") {
				result = head.step;
				break;
			}
			string a_s = alpha(head.s), b_s = beta(head.s);
			if (book.count(a_s) == 0) {
				book[a_s] = 1;
				q.push(node(a_s, head.step+1));
			}
			if (book.count(b_s) == 0) {
				book[b_s] = 1;
				q.push(node(b_s, head.step+1));
			}
		}
		printf("%d\n", result);
	}
}