題意是讓我們把一個代碼里表示的奇葩棋盤變換成一個狀態(tài)
算法就是枚舉的方法把所有的情況都表示出來 數(shù)據(jù)結(jié)構(gòu)也不難 用一個數(shù)組表達表格就好了
搜索想知道最短的話用兩種方法 一個是廣搜bfs 我自己寫的 那個判斷最后狀態(tài)我理解錯了股毫，以為只要四南窗， 實際有八個，但是我代碼還沒改過來。
bfs在這里的問題是狀態(tài)太多了以至于隊列存不下 而且速度很慢悼瓮，因為我們是一層搜完之后才搜下一層的 每個節(jié)點至多擴展出八個節(jié)點，指數(shù)一下還是很恐怖的顶吮。而且由于為了要表示三個字符的狀態(tài)總數(shù)过牙，如果直接保存三個數(shù)字的位置的話甥厦，有24！/（8寇钉！8刀疙！8！） = 9465511770 個狀態(tài) 存不下 這時候就得想想怎么壓縮了 首先 我們知道的是肯定有如此多的狀態(tài)要存 不能縮小了 因此得考慮去除掉某些信息扫倡，我們據(jù)徐==繼續(xù)使用位運算的方法思考谦秧，因為位運算通過進制轉(zhuǎn)換并不會浪費仍狀態(tài)，很自然想到把不需要關注的數(shù)字當成0好了，每次旋轉(zhuǎn)的時候我們也只判斷某個數(shù)字就行疚鲤，這樣做三次bfs就行了 這無疑費時又費力锥累，怎么辦呢？ 這時候IDA的深度搜索的優(yōu)勢就體現(xiàn)出來了 因為不用遍歷每一層 但是這種問題就是沒有深度 就是說你轉(zhuǎn)多少次都可以 但是我們可以通過迭代逐漸加深深度 然后在某個深度的某個節(jié)點大致判斷一下要不要搜下去（剪枝） （PS埃及分數(shù)那道題無法進行深度方向的剪枝 但是需要對寬度剪枝 否則深度寬度都是無窮大了）（OJ上要改一下變量名 因為更=跟一些文件重復命名了數(shù)組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;
}
