1151_魔板

题目链接：

http://soj.me/1151

题目大意：

初始矩阵为: 1 2 3 4 8 7 6 5 有A,B,C三种操作方式来变化矩阵，给定目标矩阵，求要经过多少步能得到目标矩阵，超过步数限制误解则输出-1

思路：

为了操作简单直接用了string来存储矩阵，初始直接为"12348765"，每一个状态经过三种变化可以产生三种新的状态，因此可以用宽度优先搜索来查找目标状态。因为最后还要输出变化的过程，所以对于每一个过程状态都要记录下由初始矩阵变化来的步骤。为了方便根据目标状态查找操作步骤，建立状态到步骤的映射，即用map<string,string>来存储，初始的"12348765"映射到""空的步骤，然后宽度搜索到的每个状态检查是否已经在map中，不在的话则增加进去，这样可以找到所有的状态以及得到这些状态所需的步骤的映射。

宽度优先搜索这里用了队列来实现，就是将每一层的结点全部压到队列中，每次弹出一个并将该结点的子结点全部压到队列尾部，直到队列为空。

代码：

#include <iostream>#include <string>#include <queue>#include <map>using namespace std;map<string, string> m;void build_map();void changeA(const string &s1, string &s2);void changeB(const string &s1, string &s2);void changeC(const string &s1, string &s2);int main() {	build_map();	int request_steps;	while (cin >> request_steps && request_steps != -1) {		string target;		int temp;		for (int i = 0; i < 8; ++i) {			cin >> temp;			target += string(1, ‘0‘ + temp);		}		if (m.find(target) == m.end() || m[target].size() > (unsigned)request_steps)			cout << "-1" << endl;		else			cout << m[target].size() << " " << m[target] << endl;	}	return 0;}void build_map() {	string initial_string = "12348765";	queue<string> q;	m[initial_string] = "";	q.push(initial_string);	while (!q.empty()) {		string cur = q.front(), temp = string(8, ‘ ‘);//将字符串长度初始化为8		q.pop();		changeA(cur, temp);		if(m.find(temp) == m.end()){			m[temp] = m[cur] + "A";			q.push(temp);		}		changeB(cur, temp);		if(m.find(temp) == m.end()){			m[temp] = m[cur] + "B";			q.push(temp);		}		changeC(cur, temp);		if(m.find(temp) == m.end()){			m[temp] = m[cur] + "C";			q.push(temp);		}	}}void changeA(const string &s1, string &s2) {	s2[0] = s1[4];	s2[1] = s1[5];	s2[2] = s1[6];	s2[3] = s1[7];	s2[4] = s1[0];	s2[5] = s1[1];	s2[6] = s1[2];	s2[7] = s1[3];}void changeB(const string &s1, string &s2) {	s2[0] = s1[3];	s2[1] = s1[0];	s2[2] = s1[1];	s2[3] = s1[2];	s2[4] = s1[7];	s2[5] = s1[4];	s2[6] = s1[5];	s2[7] = s1[6];}void changeC(const string &s1, string &s2) {	s2[0] = s1[0];	s2[1] = s1[5];	s2[2] = s1[1];	s2[3] = s1[3];	s2[4] = s1[4];	s2[5] = s1[6];	s2[6] = s1[2];	s2[7] = s1[7];}

Sicily 1151. 魔板 解题报告