// wangdan_qifashi.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <map>
#include <memory.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])                            //估價函數(shù)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)                              // 啟發(fā)式搜索
{
 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()                                                //主函數(shù)
{
 int i,j,k,temp[9],s;
 bool used[9] = {0};
 char op[10];
 printf("----------------------\n");
 printf("|             八數(shù)碼問題求解程序：            |\n");
 printf("| 遙感院S071班      王丹      200722130012    |\n");
 printf("|         本程序采用的是啟發(fā)式搜索方法        |\n");
 printf("----------------------\n\n\n");
 printf("本程序默認目標狀態(tài)為：\n");
 for(i = 0; i < 3; i++){
  for(j = 0; j < 3; j++){
   printf("%d ",ter[i][j]);
  }
  printf("\n");
 }
 while(1){
  printf("是否想自定義目標狀態(tài)？是請輸入y，否請輸入n:");
  scanf("%s",op);
  if(op[0] == 'y'){
   printf("請參照上面的樣式輸入目標狀態(tài)（空白位置以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("請參照上面的格式輸入初始狀態(tài)（空白位置以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("輸入錯誤(有相同數(shù)字出現(xiàn))，請重新輸入！\n");
   continue;
  }
  if((ts&1) != (tt&1)){
   printf("從初始狀態(tài)到不了目標狀態(tài)，請重新輸入。\n");
  }
  else break;
 }
 if(H(ot) == 0){
  printf("所輸入狀態(tài)就是目標狀態(tài)！\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);
 return 0;
}