题意是让我们把一个代码里表示的奇葩棋盘变换成一个状态
算法就是枚举的方法把所有的情况都表示出来 数据结构也不难 用一个数组表达表格就好了
搜索想知道最短的话用两种方法 一个是广搜bfs 我自己写的 那个判断最后状态我理解错了，以为只要四， 实际有八个，但是我代码还没改过来。
bfs在这里的问题是状态太多了以至于队列存不下 而且速度很慢，因为我们是一层搜完之后才搜下一层的 每个节点至多扩展出八个节点，指数一下还是很恐怖的。而且由于为了要表示三个字符的状态总数，如果直接保存三个数字的位置的话，有24！/（8！8！8！） = 9465511770 个状态 存不下 这时候就得想想怎么压缩了 首先 我们知道的是肯定有如此多的状态要存 不能缩小了 因此得考虑去除掉某些信息，我们据徐==继续使用位运算的方法思考，因为位运算通过进制转换并不会浪费仍状态，很自然想到把不需要关注的数字当成0好了，每次旋转的时候我们也只判断某个数字就行，这样做三次bfs就行了 这无疑费时又费力，怎么办呢？ 这时候IDA的深度搜索的优势就体现出来了 因为不用遍历每一层 但是这种问题就是没有深度 就是说你转多少次都可以 但是我们可以通过迭代逐渐加深深度 然后在某个深度的某个节点大致判断一下要不要搜下去（剪枝） （PS埃及分数那道题无法进行深度方向的剪枝 但是需要对宽度剪枝 否则深度宽度都是无穷大了）（OJ上要改一下变量名 因为更=跟一些文件重复命名了数组move）
bfs
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
/*
00 01
02 03
04 05 06 07 08 09 10
11 12
13 14 15 16 17 18 19
20 21
22 23
*/
const int move[8][7] = {
{0, 2, 6, 11, 15, 20, 22}, //A
{1, 3, 8, 12, 17, 21, 23}, //B
{10, 9, 8, 7, 6, 5, 4}, //C
{19, 18, 17, 16, 15, 14, 13}, //D
{23, 21, 17, 12, 8, 3, 1}, //E
{22, 20, 15, 11, 6, 2, 0}, //F
{13, 14, 15, 16, 17, 18, 19}, //G
{4, 5, 6, 7, 8, 9, 10}, //H
};
set<int> visit;
int maple[24], grid[24], newgrid[24];
int queue[10000];
vector<short> ans[10000];
int encode(int p[]){
int code = 0;
for(int i = 0; i < 24; i++){
if(p[i]) code = code | (1<<i);
}
return code;
}
void decode(int code, int p[]){
for(int i = 0; i < 24; i++){
if((1<<i) & code) p[i] = 1;
else p[i]= 0;
}
}
bool checkCode(int p[]){
if(p[6] && p[8] && p[15] && p[17]) return true;
return false;
}
int bfs(){
int front = 1;
int rear = 2;
visit.clear();
for(int i = 0; i < 10000; i++) ans[i].clear();
queue[front] = encode(grid);
visit.insert(queue[front]);
while(front != rear){
int code = queue[front];
decode(code, grid);
if(checkCode(grid)) return front;
front++;
for(int dir = 0; dir < 8; dir++){
memcpy(newgrid, grid, sizeof(grid));
for(int i = 0; i <= 5; i++) newgrid[move[dir][i]] = newgrid[move[dir][i+1]];
newgrid[move[dir][6]] = grid[move[dir][0]];
int newCode = encode(newgrid);
if(!visit.count(newCode)) visit.insert(newCode);
queue[rear] = newCode;
for(int i = 0; i < ans[front].size(); i++) ans[rear].push_back(ans[front][i]);
ans[rear].push_back(dir);
rear++;
if(rear > 9000) return -1;
}
}
return -1;
}
int main(){
while(scanf("%d", &maple[0]) == 1 && maple[0]){
for(int i = 1; i < 24; i++) scanf("%d", &maple[i]);
int res = 200000;
for(int select = 1; select <= 3; select++){
for(int i = 0; i < 24; i++){
if(maple[i] != select) grid[i] = 0;
else grid[i] = 1;
}
// printf("encode = %d\n", encode(grid));
// decode(encode(grid), newgrid);
// for(int i = 0; i < 24; i++) printf("%d ",newgrid[i]);
// printf("\n");
// for(int dir = 0; dir < 8; dir++){
// memcpy(newgrid, grid, sizeof(grid));
// for(int i = 0; i <= 5; i++) newgrid[move[dir][i]] = newgrid[move[dir][i+1]];
// newgrid[move[dir][6]] = grid[move[dir][0]];
// printf("direction %d\n", dir);
// for(int i = 0; i < 24; i++) printf("%d ",newgrid[i]);
// printf("\n");
// }
int flag = bfs();
printf("flag=%d ", flag);
if(flag != -1){
for(int i = 0; i < ans[flag].size(); i++) printf("%d ", ans[flag][i]);
}
printf("\n");
}
printf("ans = %d\n", res);
}
return 0;
}
IDA
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
/*
00 01
02 03
04 05 06 07 08 09 10
11 12
13 14 15 16 17 18 19
20 21
22 23
*/
const int move[8][7] = {
{0, 2, 6, 11, 15, 20, 22}, //A
{1, 3, 8, 12, 17, 21, 23}, //B
{10, 9, 8, 7, 6, 5, 4}, //C
{19, 18, 17, 16, 15, 14, 13}, //D
{23, 21, 17, 12, 8, 3, 1}, //E
{22, 20, 15, 11, 6, 2, 0}, //F
{13, 14, 15, 16, 17, 18, 19}, //G
{4, 5, 6, 7, 8, 9, 10} //H
};
const int back[8] = {5, 4, 7, 6, 1, 0, 3, 2};
const int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};
char ans[100];
int maple[24];
bool is_final(){
for(int i = 1; i < 8; i++)
if(maple[center[i]] != maple[center[0]]) return false;
return true;
}
int h(){
int dif[4];
memset(dif, 0, sizeof(dif));
for(int num = 1; num <= 3; num++)
for(int i = 0; i < 8; i++)
if(maple[center[i]] != num) dif[num]++;
int res = 1000;
for(int num = 1; num <= 3; num++) res = min(res, dif[num]);
return res;
}
void change(int dir){
int temp;
//int a = move[dir][0];
temp = maple[move[dir][0]];
for(int i = 0; i <= 5; i++) maple[move[dir][i]] = maple[move[dir][i+1]];
maple[move[dir][6]] = temp;
}
bool dfs(int d, int maxd){ //IDA框架
if(is_final()){
ans[d] = '\0';
printf("%s\n", ans);
return true;
}
if(d + h() > maxd) return false;
for(int dir = 0; dir < 8; dir++){
ans[d] = 'A' + dir;
change(dir);
if(dfs(d+1, maxd)) return true;
change(back[dir]);
}
return false;
}
int main(){
while(scanf("%d", &maple[0]) && maple[0]){
for(int i = 1; i < 24; i++) scanf("%d", &maple[i]);
if(is_final()) {
printf("No moves needed\n");
} else {
int maxd;
for( maxd = 1; ; maxd++){
if(dfs(0, maxd)){
break;
}
}
}
printf("%d\n", maple[6]);
}
return 0;
}
