//---------------------------------------------------------------------------

#include <stdio.h>

#include <conio.h>

//---------------------------------------------------------------------------

//--以下定義一些常數或參數--

//---------------------------------------------------------------------------

//棋盤表示使用char一維數組,例:char q[20];

//用1-15表示各棋子,空位用0表示,兵1-4,豎將5-9,橫將10-14,大王15

//大王只能1個,將必須5個(橫豎合計),兵必須為4個

const char U[]="ABBBBCCCCCHHHHHM";; //棋子類型表

const COL[20]={0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3};   //列號表

const ROW[20]={0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4};   //行號表

const WQ2[13]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096}; //二進制位權表(12個)

//---------------------------------------------------------------------------

//--以下定義幾函數--

//---------------------------------------------------------------------------

//以下define用于棋盤復制,不要用環循,實地址直接引用要快8倍

#define qpcpy(q1,q2) {/*復制棋盤*/\

  int *ls1=(int*)q1,*ls2=(int*)q2;\

  ls1[0]=ls2[0],ls1[1]=ls2[1],ls1[2]=ls2[2],ls1[3]=ls2[3],ls1[4]=ls2[4];\

}

//memset(JD,0,Bm.bmtot);

void qkmem(void *ps,int n){ //內存塊置0

  register int *p=(int*)ps,*p2=p+n/4;

  while(p<p2) *p++=0;

  char *p3=(char *)p,*p4=(char *)ps+n;

  while(p3<p4) *p3++=0;

}

void prt(char *q){ //打印棋盤

  int i,j;

  for(i=0;i<5;i++){

    for(j=0;j<4;j++) printf("%2d ",q[i*4+j]);

    printf("\r\n");

  }

  printf("\r\n");

}

//---------------------------------------------------------------------------

//--以下是搜索算法之一(解決編碼問題)--

//---------------------------------------------------------------------------

class PmBm{ //盤面編碼類

 public:

 short int *Hz,*Sz,*Bz;  //豎將,橫將,小兵,組合序號表

 int *Hw,*Sw,Mw[12]; //權值表:橫條,豎條,大王

 int bmtot;

 PmBm(char *q){//初始化編碼表

   Hz=new short int[4096*3]; Sz=Hz+4096; Bz=Hz+4096*2;

   Hw =new int[792*2];  Sw=Hw+792;  //C12取5=792

   int i,j,k;

   int Hn=0,Bn=0,Sn=0; //各類子數目,大王默認為1不用計數

   for(i=0;i<20;i++){   //計算各種棋子的個數

     if(U[q[i]]=='B') Bn++;

     if(U[q[i]]=='H') Hn++;

     if(U[q[i]]=='C') Sn++;

   }

   Hn/=2,Sn/=2;

   int Hmax=WQ2[11],Smax=WQ2[12-Hn*2],Bmax=WQ2[16-(Hn+Sn)*2]; //各種子的最大二進位數

   int Hx=0,Sx=0,Bx=0; //各種棋子組合的最大序號

   for(i=0;i<4096;i++){  //初始化組合序號表

     for(j=0,k=0;j<12;j++) if(i&WQ2[j]) k++; //計算1的個數

     if(k==Hn&&i<Hmax) Hz[i]=Hx++;

     if(k==Sn&&i<Smax) Sz[i]=Sx++;

     if(k==Bn&&i<Bmax) Bz[i]=Bx++;

   }

   int Sq=Bx,Hq=Bx*Sx,Mq=Bx*Sx*Hx; //豎將位權,橫將位權,王位權

   for(i=0;i<12;i++) Mw[i]=i*Mq; //初始化大王權值表

   for(i=0;i<Hx;i++) Hw[i]=i*Hq; //初始化橫將權值表

   for(i=0;i<Sx;i++) Sw[i]=i*Sq; //初始化豎將權值表

   bmtot=Mq*12;

 }

 ~PmBm(){ delete[] Hz,Hw; }

 int BM(char *q){ //盤面編碼

   int Bb=0,Bd=-1; //空位序號記錄器

   int Sb=0,Sd=-1; //豎條序號記錄器

   int Hb=0,Hd=-1; //橫條序號記錄器

   int Mb;         //大王序號記錄器

   char c,lx,f[16]={0};   //其中f[]標記幾個棋子是否已確定位置序號

   int i;

   for(i=0;i<20;i++){

     c=q[i],lx=U[c]; //當前的值

     if(lx=='M') { //大王定序

       if(!f[c]) Mb=i-ROW[i],f[c]=1;

       continue;

     }

     if(COL[i]<3&&U[q[i+1]]<='H') Hd++; //橫條位置序號(編號)

     if(lx=='H') {//橫將定序,轉為二進制進行詢址得Hb

       if(!f[c]) Hb+=WQ2[Hd],f[c]=1;

       continue;

     }

     if(ROW[i]<4&&U[q[i+4]]<='C') Sd++; //豎將位置序號(編號)

     if(lx=='C') { //豎條定序,轉為二進制進行詢址得Sb

       if(!f[c]) Sb+=WQ2[Sd],f[c]=1;

       continue;

     }

     if(lx<='B') Bd++;  //小兵位置序號(編號)

     if(lx=='B') Bb+=WQ2[Bd]; //小兵定序,轉為二進制進行詢址得Bb

   }

   //Hb,Sb,Bb為組合序號,"橫刀立馬"最大值為小兵C(6,4)-1=15-1,豎條C(10,4)-1=210-1

   Bb=Bz[Bb],Sb=Sz[Sb],Hb=Hz[Hb];//詢址后得得Bb,Sb,Hb組合序號

   return Bb+Sw[Sb]+Hw[Hb]+Mw[Mb]; //用位權編碼,其中Bb的位權為1

 }

 int dcBM(char *q){ //按左右對稱規則考查棋盤,對其編碼

   char i,q2[20];

   for(i=0;i<20;i+=4) q2[i]=q[i+3],q2[i+1]=q[i+2],q2[i+2]=q[i+1],q2[i+3]=q[i];

   return BM(q2);

 }

};

//---------------------------------------------------------------------------

//以下定義搜索過程使用的核心數據結構

//---------------------------------------------------------------------------

struct PMZB{ //盤面走步集結構

  char s[10],d[10];//原位置,目標位置,最多只會有10步

  int n;           //總步數

};

//以下是走法生成器函數

#define kgpd(i)  (i==k1||i==k2) //空格判斷宏

#define kgpd1(i) (i==k1&&h==1)  //豎聯空格判斷宏

#define kgpd2(i) (i==k1&&h==2)  //橫聯空格判斷宏

#define zin(des) z->s[z->n]=i,z->d[z->n]=des,z->n++ //保存步法宏

void zbFX(char *q,PMZB *z){ //分析當前可能的步法,并將所有可能的步法保存在z中

  int i,col,k1=0,k2=0,h=0; //i,列,空格1位置,空格2位置,h為兩空格的聯合類型

  char c,lx,f[16]={0}; //f[]記錄已判斷過的棋字

  z->n=0; //計步復位

 

  for(i=0;i<20;i++){

    if(!q[i]) k1=k2,k2=i; //查空格的位置

  }

  if(k1+4==k2) h=1;            //空格豎聯合

  if(k1+1==k2&&COL[k1]<3) h=2; //空格橫聯合

  for(i=0;i<20;i++){

    c=q[i],lx=U[c],col=COL[i];

    if(f[c]) continue;

    switch(lx){

     case 'M': //曹操可能的走步

       if(kgpd2(i+8))        zin(i+4);  //向下

       if(kgpd2(i-4))        zin(i-4);  //向上

       if(col<2&&kgpd1(i+2)) zin(i+1);  //向右

       if(col  &&kgpd1(i-1)) zin(i-1);  //向左

       f[c]=1; break;

     case 'H': //關羽可能的走步

       if(kgpd2(i+4))        zin(i+4);  //向下

       if(kgpd2(i-4))        zin(i-4);  //向上

       if(col<2&&kgpd(i+2)) {zin(i+1); if(h==2) zin(k1); }  //向右

       if(col  &&kgpd(i-1)) {zin(i-1); if(h==2) zin(k1); }  //向左

       f[c]=1; break;

     case 'C': //張飛,馬超,趙云,黃忠可能的走步

       if(kgpd(i+8))        {zin(i+4); if(h==1) zin(k1); }  //向下

       if(kgpd(i-4))        {zin(i-4); if(h==1) zin(k1); }  //向上

       if(col<3&&kgpd1(i+1)) zin(i+1);  //向右

       if(col  &&kgpd1(i-1)) zin(i-1);  //向左

       f[c]=1; break;

     case 'B': //小兵可能的走步

       if(kgpd(i+4))        { if(h){zin(k1);zin(k2);} else zin(i+4); } //向上

       if(kgpd(i-4))        { if(h){zin(k1);zin(k2);} else zin(i-4); } //向下

       if(col<3&&kgpd(i+1)) { if(h){zin(k1);zin(k2);} else zin(i+1); } //向右

       if(col  &&kgpd(i-1)) { if(h){zin(k1);zin(k2);} else zin(i-1); } //向右

       break;

    }

  }

}

void zb(char *q,int s,int d){ //走一步函數

  char c=q[s],lx=U[c];

  switch(lx){

    case 'B': {q[s]=0;        q[d]=c;          break; }

    case 'C': {q[s]=q[s+4]=0; q[d]=q[d+4]=c;   break; }

    case 'H': {q[s]=q[s+1]=0; q[d]=q[d+1]=c;   break; }

    case 'M': {q[s]=q[s+1]=q[s+4]=q[s+5]=0; q[d]=q[d+1]=q[d+4]=q[d+5]=c; break; }

  }

}

//---------------------------------------------------------------------------

//--以下是搜索過程（廣度優先）--

//---------------------------------------------------------------------------

class ZBD{ //走步隊

 public:

 char (*z)[20];     //隊列

 PMZB zbj;

 int n;       //隊長度

 int *hs,*hss;//回溯用的指針及棋子

 int m,cur;   //隊頭及隊頭內步集游標,用于廣度搜索

 int max;     //最大隊長

 int *res,ren;//結果

 ZBD(int k){ z=new char[k][20]; hs=new int[k*2+500]; hss=hs+k; res=hss+k; max=k; reset(); }

 ~ZBD(){ delete[] z; delete[] hs;}

 void reset() { n=0; m=0,cur=-1; hss[n]=-1; ren=0;}

 int zbcd(char *q){ //走步出隊

   if(cur==-1) zbFX(z[m],&zbj);

   cur++; if(cur>=zbj.n) {m++,cur=-1; return 1;} //步集游標控制

   if(hss[m]==zbj.s[cur]) return 1;//和上次移動同一個棋子時不搜索,可提速20%左右

   qpcpy(q,z[m]); zb(q,zbj.s[cur],zbj.d[cur]); //走步后產生新節點,結果放在q中

   return 0;

 }

 void zbrd(char *q){ //走步入隊

   if(n>=max) { printf("隊溢出.\r\n"); return; }

   qpcpy(z[n],q); //出隊

   if(cur>=0) hss[n]=zbj.d[cur]; //記錄移動的子(用于回溯)

   hs[n++]=m; //記錄回溯點

 }

 void hui(int cs){ //參數:層數

   int k=cs-2; ren=cs,res[cs-1]=m;

   for(;k>=0;k--) res[k]=hs[res[k+1]]; //回溯

 }

 char* getre(int n){ return z[res[n]];} //取第n步盤面

 

};

//--廣度優先--

void bfs(char *q,int dep){ //參數為棋盤及搜索最大深度

  int i,j,k,bm,v; //ok表示是否找到

  int js=0,js2=0;

  PmBm Bm(q); //建立編碼器

  char *JD=new char[Bm.bmtot]; qkmem(JD,Bm.bmtot); //建立節點數組

  ZBD Z=ZBD(Bm.bmtot/10); //建立隊

  for(Z.zbrd(q),i=1;i<=dep;i++){ //一層一層的搜索

    k=Z.n;

    //printf("本層%d %d\r\n",i,k-Z.m);

    while(Z.m<k){ //廣度優先

      if(Z.zbcd(q)) continue;     //返回1說明是步集出隊,不是步出隊

      js++;

      if(q[17]==15&&q[18]==15) { Z.hui(i); goto end; }//大王出來了

      if(i==dep) continue; //到了最后一層可以不再入隊了

      bm=Bm.BM(q);

      if(!JD[bm]){

        js2++ ;  //js搜索總次數計數和js2遍歷的實結點個數

        JD[bm]=1, JD[Bm.dcBM(q)]=1;//對節點及其對稱點編碼

        Z.zbrd(q);

      }

    }

  }

  end:delete JD;

  printf("共遍歷%d個節點,其中實結點%d.隊長%d,搜索層數%d,任意鍵...\r\n",js,js2,Z.n,Z.ren);

  if(!Z.ren) { printf("此局%d步內無解",dep); return; }

  for(i=0;i<Z.ren;i++) { getch();clrscr(); prt(Z.getre(i)); } //輸出結果

}

//---------------------------------------------------------------------------

void main(int argc, char* argv[])

{//華榮道棋盤參數,須留二個空位,兵4個1-4,豎將5-9,橫將10-14,大王15(1個)

 char qp[20]={

   6,15,15,7,

   6,15,15,7,

   8,11,11,5,

   8,3, 4, 5,

   2,0, 0, 1

 };

 int i,dep=81;

 bfs(qp,dep);

 getch();

}