a197p的专栏

因为8个转轮对应的位置比较没有规律,需要提前将这些位置存在数组中,方便旋转操作和回溯法的归位操作。

利用数组来人为储存没有规律的数字。

IDA*合了bfs步数最少和dfs字典序最小的优点。

#include<cstdio>#include<algorithm>#define maxn 500using namespace std;int block[24];int roller[8][7]={{0,2,6,11,15,20,22},{1,3,8,12,17,21,23},{10,9,8,7,6,5,4},{19,18,17,16,15,14,13},{23,21,17,12,8,3,1},{22,20,15,11,6,2,0},{13,14,15,16,17,18,19},{4,5,6,7,8,9,10}};int back[8]={5,4,7,6,1,0,3,2};int goalpos[8] = {6,7,8,11,12,15,16,17};int op[100000];int rot(int *blk,int dir){for(int i=1;i<7;i++){int tmp = blk[roller[dir][i]];blk[roller[dir][i]] = blk[roller[dir][i-1]];blk[roller[dir][i-1]]=tmp;}}int dfs(int d,int maxd){if(d == maxd){int ok=1;for(int i=1;i<8;i++){if(block[goalpos[i]]!=block[goalpos[i-1]]){ok=0;break;}}if(ok){if(!d){printf("No moves needed\n%d\n",block[6]);return 1;}for(int i=0;i<d;i++) printf("%c",op[i]+'A');printf("\n%d\n",block[6]);return 1;}return 0;}else {int diff=0;int a=0,b=0,c=0;for(int i=0;i<8;i++){if(block[goalpos[i]]==1) a++;if(block[goalpos[i]]==2) b++;if(block[goalpos[i]]==3) c++;}diff = 8-max(max(a,b),c);if(d + diff > maxd) return 0;for(int i=0;i<8;i++){op[d]=i;rot(block,i);if(dfs(d+1,maxd)) return 1;rot(block, back[i]);}}return 0;}int main(){while(1){for(int i=0;i<24;i++){scanf("%d",&block[i]);if(!block[i]) return 0;}for(int maxd=0;;maxd++){if(dfs(0,maxd)){break;}}}return 0;}

,人生如果错了方向,停止就是进步”。

a197p的专栏

相关文章:

你感兴趣的文章:

标签云: