八数码问题（DOS)

#include <stdio.h> #include <map> #include <memory.h> #include <stdlib.h> #include <time.h> using namespace std; #define SIZE 1000000 struct QUEUE{ int data,pre,f,deep; }heap[SIZE]; //用顺序结构定义一个最小二叉堆 int pout,tail,ter[3][3] = {{1,2,3},{8,0,4},{7,6,5}},sta[9]; //定义目标状态 struct OUT{ int data,pre; }out[SIZE]; void swap(QUEUE &a, QUEUE &b) //结构体交换值 { int temp = a.data; a.data = b.data; b.data = temp; temp = a.pre; a.pre = b.pre; b.pre = temp; temp = a.f; a.f = b.f; b.f = temp; temp = a.deep; a.deep = b.deep; b.deep = temp; } QUEUE pop() //进堆栈 { int p,t; swap(heap[1],heap[tail]); tail--; p = 1; while((t = 2*p) <= tail){ if(t+1 <= tail && heap[t].f > heap[t+1].f) t++; if(heap[p].f > heap[t].f){ swap(heap[p],heap[t]); p = t; } else break; } return heap[tail+1]; } void push(QUEUE a) //出堆栈 { int p,t; tail++; heap[tail].data = a.data; heap[tail].f = a.f; heap[tail].pre = a.pre; heap[tail].deep = a.deep; p = tail; while((t = p/2) >= 1){ if(heap[t].f > heap[p].f) swap(heap[t],heap[p]); else break; } } int nxnum(int p[9]) //求逆序对 { int i,j,re = 0; for(i = 0; i < 8; i++){ if(p[i] == 0) continue; for(j = i+1; j < 9; j++){ if(p[j] == 0) continue; if(p[i] > p[j]) re++; } } return re; } int H(int p[3][3]) //估价函数h { int i,j,re = 0; for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ if(p[i][j] != ter[i][j]) re++; } } return re; } bool astar(int s) // A*搜索 { map<int,int>mp; tail = 1; heap[1].data = s; heap[1].pre = -1; heap[1].deep = 0; out[0].data = s; out[0].pre = -1; pout = 0; QUEUE tstatu,add; int temp[3][3],i,j,tf,x,y,tt[3][3]; while(tail >= 1){ tstatu = pop(); out[++pout].data = tf = tstatu.data; out[pout].pre = tstatu.pre; for(i = 2; i >= 0; i--){ for(j = 2; j >= 0; j--){ temp[i][j] = tf%10; if(temp[i][j] == 0){ x = i; y = j; } tf /= 10; } } if(x > 0){ // 上移 for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ tt[i][j] = temp[i][j]; } } tf = tt[x][y]; tt[x][y] = tt[x-1][y]; tt[x-1][y] = tf; tf = 0; for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ tf = tf*10 + tt[i][j]; } } if(mp[tf] == 0){ mp[tf] = 1; add.data = tf; add.deep = tstatu.deep+1; i = H(tt); add.f = add.deep + i; add.pre = pout; if(i == 0) return true; push(add); } } if(y > 0){ //左移 for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ tt[i][j] = temp[i][j]; } } tf = tt[x][y]; tt[x][y] = tt[x][y-1]; tt[x][y-1] = tf; tf = 0; for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ tf = tf*10 + tt[i][j]; } } if(mp[tf] == 0){ mp[tf] = 1; add.data = tf; add.deep = tstatu.deep+1; i = H(tt); add.f = add.deep + i; add.pre = pout; if(i == 0) return true; push(add); } } if(x < 2){ //下移 for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ tt[i][j] = temp[i][j]; } } tf = tt[x][y]; tt[x][y] = tt[x+1][y]; tt[x+1][y] = tf; tf = 0; for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ tf = tf*10 + tt[i][j]; } } if(mp[tf] == 0){ mp[tf] = 1; add.data = tf; add.deep = tstatu.deep+1; i = H(tt); add.f = add.deep + i; add.pre = pout; if(i == 0) return true; push(add); } } if(y < 2){ //右移 for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ tt[i][j] = temp[i][j]; } } tf = tt[x][y]; tt[x][y] = tt[x][y+1]; tt[x][y+1] = tf; tf = 0; for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ tf = tf*10 + tt[i][j]; } } if(mp[tf] == 0){ mp[tf] = 1; add.data = tf; add.deep = tstatu.deep; i = H(tt); add.f = add.deep + i; add.pre = pout; if(i == 0) return true; push(add); } } } return false; } int no = 1,ot[3][3]; void print(int k) // 打印结果 { if(out[k].pre != -1){ print(out[k].pre); int i,j,f = out[k].data,tt; printf("第%d步:\n",no++); for(i = 2; i >= 0; i--){ for(j = 2; j >= 0; j--){ ot[i][j] = f%10; f /= 10; } } for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ if(ot[i][j] == 0) printf(" "); else printf("%d ",ot[i][j]); } printf("\n"); } printf("\n"); } } int main(void) { int i,j,k,temp[9],s; bool used[9] = {0}; char op[10]; printf("----------------------\n"); printf("|八数码问题求解程序：|\n"); printf("|计05-3班 白希玮 段晶 张雪颖 赵妍 张晓倩 曾思达 |\n"); printf("----------------------\n\n\n"); printf("本程序默认目标状态为：\n"); for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ printf("%d ",ter[i][j]); } printf("\n"); } while(1){ printf("取消请输入y，确认请输入n:"); scanf("%s",op); if(op[0] == 'y'){ printf("请参照上面的样式输入目标状态（空白位置以0代替）:\n"); for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ scanf("%d",&ter[i][j]); } } } else if(op[0] != 'n') printf("输入错误！\n"); else break; } while(1){ printf("请参照上面的格式输入初始状态（空白位置以0代替）:\n"); k = 0; bool error = false; memset(used,0,sizeof(used)); for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ scanf("%d",&sta[k]); ot[i][j] = sta[k]; if(used[sta[k]]){ error = true; } used[sta[k]] = 1; temp[k++] = ter[i][j]; } } int ts = nxnum(sta); int tt = nxnum(temp); if(error){ printf("输入错误(有相同数字出现)，请重新输入！\n"); continue; } if((ts&1) != (tt&1)){ printf("从初始状态到不了目标状态，请重新输入。\n"); } else break; } if(H(ot) == 0){ printf("所输入状态就是目标状态！\n"); return 0; } s = 0; for(i = 0; i < 9; i++){ s = s*10 + sta[i]; } astar(s); print(pout); printf("第%d步:\n",no); for(i = 0; i < 3; i++){ for(j = 0; j < 3; j++){ if(ter[i][j] == 0) printf(" "); else printf("%d ",ter[i][j]); } printf("\n"); } printf("共走了%d步。\n",no); long t = 10000000L;