題目
Constraints
Time Limit: 1 secs, Memory Limit: 32 MB , Special Judge
Description
魔板由8個(gè)大小相同方塊組成笼沥，分別用涂上不同顏色做院，用1到8的數(shù)字表示蝠咆。
其初始狀態(tài)是
1 2 3 4
8 7 6 5
對(duì)魔板可進(jìn)行三種基本操作：
A操作（上下行互換）：
8 7 6 5
1 2 3 4
B操作（每次以行循環(huán)右移一個(gè)）：
4 1 2 3
5 8 7 6
C操作（中間四小塊順時(shí)針轉(zhuǎn)一格）：
1 7 2 4
8 6 3 5
用上述三種基本操作聪舒，可將任一種狀態(tài)裝換成另一種狀態(tài)喜滨。
Input
輸入包括多個(gè)要求解的魔板词身，每個(gè)魔板用三行描述佛掖。
第一行步數(shù)N（不超過10的整數(shù)）练湿，表示最多容許的步數(shù)猴仑。
第二、第三行表示目標(biāo)狀態(tài)肥哎，按照魔板的形狀辽俗，顏色用1到8的表示。
當(dāng)N等于-1的時(shí)候篡诽，表示輸入結(jié)束崖飘。
Output
對(duì)于每一個(gè)要求解的魔板，輸出一行杈女。
首先是一個(gè)整數(shù)M朱浴，表示你找到解答所需要的步數(shù)。接著若干個(gè)空格之后达椰，從第一步開始按順序給出M步操作（每一步是A翰蠢、B或C），相鄰兩個(gè)操作之間沒有任何空格啰劲。
注意：如果不能達(dá)到梁沧，則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
評(píng)分：M超過N或者給出的操作不正確均不能得分蝇裤。
思路
- 封裝魔板的狀態(tài)趁尼，每個(gè)狀態(tài)對(duì)應(yīng)一個(gè)到達(dá)此狀態(tài)的最優(yōu)路徑
- 用廣度搜索來獲得每個(gè)狀態(tài)的最優(yōu)路徑。例如猖辫，AA、BBBB砚殿、CCCC這幾個(gè)操作是沒有效果的啃憎，所以可以把一個(gè)已經(jīng)遍歷的過的狀態(tài)放在
closed表里面，這樣就可以利用已經(jīng)遍歷過的狀態(tài)簡化似炎。 - 把所有步數(shù)小于等于N的狀態(tài)都查找過了辛萍，才算是查找完成悯姊。
代碼
剪枝版代碼
// 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;
}
