题目
Constraints
Time Limit: 1 secs, Memory Limit: 32 MB , Special Judge
Description
魔板由8个大小相同方块组成，分别用涂上不同颜色，用1到8的数字表示。
其初始状态是
1 2 3 4
8 7 6 5
对魔板可进行三种基本操作：
A操作（上下行互换）：
8 7 6 5
1 2 3 4
B操作（每次以行循环右移一个）：
4 1 2 3
5 8 7 6
C操作（中间四小块顺时针转一格）：
1 7 2 4
8 6 3 5
用上述三种基本操作，可将任一种状态装换成另一种状态。
Input
输入包括多个要求解的魔板，每个魔板用三行描述。
第一行步数N（不超过10的整数），表示最多容许的步数。
第二、第三行表示目标状态，按照魔板的形状，颜色用1到8的表示。
当N等于-1的时候，表示输入结束。
Output
对于每一个要求解的魔板，输出一行。
首先是一个整数M，表示你找到解答所需要的步数。接着若干个空格之后，从第一步开始按顺序给出M步操作（每一步是A、B或C），相邻两个操作之间没有任何空格。
注意：如果不能达到，则M输出-1即可。
Sample Input
4
5 8 7 6
4 1 2 3
3
8 7 6 5
1 2 3 4
-1
Sample Output
2 AB
1 A
评分：M超过N或者给出的操作不正确均不能得分。
思路
- 封装魔板的状态，每个状态对应一个到达此状态的最优路径
- 用广度搜索来获得每个状态的最优路径。例如，AA、BBBB、CCCC这几个操作是没有效果的，所以可以把一个已经遍历的过的状态放在
closed表里面，这样就可以利用已经遍历过的状态简化。 - 把所有步数小于等于N的状态都查找过了，才算是查找完成。
代码
剪枝版代码
// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
// 1150 简单魔板: http://soj.sysu.edu.cn/1150
#include <cstdio>
#include <string>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int state[2][4];
string opt;
};
Node doA(Node node);
Node doB(Node node);
Node doC(Node node);
bool isEqualState(Node A, Node B);
int find(vector<Node> closed, Node tofind);
int main() {
int maxSteps;
Node aim;
Node start;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 4; j++) {
if (!i) {
start.state[i][j] = j + 1;
} else {
start.state[i][j] = 8 - j;
}
}
}
while (scanf("%d", &maxSteps) != EOF && maxSteps != -1) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 4; j++) {
scanf("%d", &aim.state[i][j]);
}
}
vector<Node> closed;
queue<Node> que;
que.push(start);
// closed.push_back(start);
while (!que.empty()) {
Node current = que.front();
que.pop();
if (current.opt.size() > maxSteps) {
printf("-1\n");
break;
}
if (isEqualState(current, aim)) {
printf("%d %s\n", current.opt.size(), current.opt.c_str());
break;
}
int index = find(closed, current);
if (index != -1) {
current = closed[index];
} else {
closed.push_back(current);
}
Node Anext = doA(current);
if (find(closed, Anext) == -1) que.push(Anext);
Node Bnext = doB(current);
if (find(closed, Bnext) == -1) que.push(Bnext);
Node Cnext = doC(current);
if (find(closed, Cnext) == -1) que.push(Cnext);
}
}
return 0;
}
Node doA(Node node) {
Node Anext;
for (int i = 0; i < 4; i++) {
Anext.state[0][i] = node.state[1][i];
Anext.state[1][i] = node.state[0][i];
}
Anext.opt = node.opt + 'A';
return Anext;
}
Node doB(Node node) {
Node Bnext;
for (int i = 0; i < 4; i++) {
Bnext.state[0][i] = node.state[0][(i - 1 + 4) % 4];
Bnext.state[1][i] = node.state[1][(i - 1 + 4) % 4];
}
Bnext.opt = node.opt + 'B';
return Bnext;
}
Node doC(Node node) {
Node Cnext;
for (int i = 0; i < 4; i++) {
Cnext.state[0][i] = node.state[0][i];
Cnext.state[1][i] = node.state[1][i];
}
Cnext.state[0][1] = node.state[1][1];
Cnext.state[0][2] = node.state[0][1];
Cnext.state[1][1] = node.state[1][2];
Cnext.state[1][2] = node.state[0][2];
Cnext.opt = node.opt + 'C';
return Cnext;
}
bool isEqualState(Node A, Node B) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 4; j++) {
if (A.state[i][j] != B.state[i][j]) return false;
}
}
return true;
}
int find(vector<Node> closed, Node tofind) {
for (int i = 0; i < closed.size(); i++) {
if (isEqualState(closed[i], tofind)) return i;
}
return -1;
}
