?? huarongdaojavashixian.txt
字號:
printf("\r\n");
}
}
//---------------------------------------------------------------------------
void main(int argc, char* argv[]){
int i,ok,t1=clock();
QP qp={
3,5,5,3,
1,1,1,1,
3,4,4,3,
1,2,2,1,
2,0,0,2
};
ok=S.bfs(qp,500);
if(!ok) printf("此局500層內無解.\r\n");
if(ok==-1) printf("此局無解.\r\n",200);
printf("%d層有解,遍歷%d節(jié)點,哈希%d節(jié)點,隊長%d,哈希沖突%d次,用時%dms\r\n",S.ren,S.js,S.js2,S.dn,S.Hx.cht,clock()-t1);
for(i=0;i<S.ren;i++) {
printf("第%d步(ESC退出)\r\n",i);
prt(S.getre(i));
if(getch()==27) break;
clrscr();
}
getch();
}
//---------------------------------------------------------------------------
八、利用javascript進行華榮道搜索
//===============================================
//===============================================
//===============================================
//下文是利用javascript進行華容道搜索
//速度：約25秒(P2.4G)
//設計：許劍偉,2006年5月5日下午及晚上—2006年5月6日上午
//===============================================
<html>
<head>
<title>華容道</title>
</head>
<body>
<script language=javascript>
var QZLX=Array();//棋子類型表
QZLX.A="A";
QZLX.B="B";
QZLX.X="B";
QZLX.Y="B";
QZLX.Z="B";
QZLX.C="C";QZLX.D="C";QZLX.E="C";QZLX.F="C";QZLX.G="C";
QZLX.H="H";QZLX.I="H";QZLX.J="H";QZLX.K="H";QZLX.L="H";
QZLX.M="M";
var COL=Array(0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3); //列號表
var ROW=Array(0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4); //行號表
qp=Array(
"C","M","M","D",
"C","M","M","D",
"E","H","H","F",
"E","X","Y","F",
"B","A","A","Z"
// "B","M","M","B",
// "E","M","M","F",
// "E","H","H","F",
// "B","I","I","B",
// "A","J","J","A"
// "M","M","A","C",
// "M","M","A","C",
// "D","E","H","H",
// "D","E","B","F",
// "B","B","B","F"
);
function qpToS(q){ //棋盤轉為串
var i,j,s="";
for(i=0;i<5;i++,s+="<br>")
for(j=0;j<4;j++) s+=q[i*4+j]+" ";
return s.replace(/[A]/g," ");
}
function BM(q){ //快速編碼
return q.join("").replace(/[DEFG]/g,"C").replace(/[IJKL]/g,"H").replace(/[XYZ]/g,"B");
}
function dcBM(q){ //對稱編碼
var s=q[3]+q[2]+q[1]+q[0]+q[7]+q[6]+q[5]+q[4]+q[11]+q[10]+q[9]+q[8]+q[15]+q[14]+q[13]+q[12]+q[19]+q[18]+q[17]+q[16];
return s.replace(/[DEFG]/g,"C").replace(/[IJKL]/g,"H").replace(/[XYZ]/g,"B");
}
function zbFX(q){ //走步分析
var i,r="";
for(i in q){ //i是字符型
if(q[i-0]!="A") continue;
i=i-0;
if(ROW[i]<4){
switch(QZLX[q[i+4]]){ //下棋子
case "B": { r+=i+4+" "+i+" "; break; }
case "C": { r+=i+4+" "+i+" "; break; }
case "H": if(q[i+4]==q[i+5]&&q[i+1]=="A") { r+=i+4+" "+i+" "; break; }
case "M": if(q[i+4]==q[i+5]&&q[i+1]=="A") { r+=i+4+" "+i+" "; }
}
if(q[i+4]=="A"&&ROW[i]<3){ //處理下二棋子
switch(QZLX[q[i+8]]){
case "C": { r+=i+8+" "+i+" "; break; }
case "B": { r+=i+8+" "+i+" "; }
}
}
}
if(ROW[i]){
switch(QZLX[q[i-4]]){ //上棋子
case "B": { r+=i-4+" "+i+" "; break; }
case "C": { r+=i-8+" "+(i-4)+" "; break; }
case "H": if(q[i-4]==q[i-3]&&q[i+1]=="A") { r+=i-4+" "+i+" "; break; }
case "M": if(q[i-4]==q[i-3]&&q[i+1]=="A") { r+=i-8+" "+(i-4)+" "; }
}
if(q[i-4]=="A"&&ROW[i]>1){ //處理上二棋子
switch(QZLX[q[i-8]]){
case "C": { r+=i-12+" "+(i-4)+" "; break; }
case "B": { r+=i-8+" "+i+" "; }
}
}
}
if(COL[i]){ //處理左邊棋子
switch(QZLX[q[i-1]]){ //左棋子
case "B": { r+=i-1+" "+i+" "; break; }
case "H": { r+=i-2+" "+(i-1)+" "; break; }
case "C": if(q[i-1]==q[i+3]&&q[i+4]=="A") { r+=i-1+" "+i+" "; break; }
case "M": if(q[i-1]==q[i+3]&&q[i+4]=="A") { r+=i-2+" "+(i-1)+" "; }
}
if(q[i-1]=="A"&&COL[i]>1){ //處理左二棋子
switch(QZLX[q[i-2]]){
case "H": { r+=i-3+" "+(i-1)+" "; break; }
case "B": { r+=i-2+" "+i+" "; }
}
}
if(QZLX[q[i-5]]=="B"&&(q[i-1]=="A"||q[i-4]=="A")) { r+=i-5+" "+i+" "; } //左上方棋子
if(QZLX[q[i+3]]=="B"&&(q[i-1]=="A"||q[i+4]=="A")) { r+=i+3+" "+i+" "; } //左下方棋子
}
if(COL[i]<3){ //處理右邊棋子
switch(QZLX[q[i+1]]){ //右棋子
case "B": { r+=i+1+" "+i+" "; break; }
case "H": { r+=i+1+" "+i+" "; break; }
case "C": if(q[i+1]==q[i+5]&&q[i+4]=="A") { r+=i+1+" "+i+" "; break; }
case "M": if(q[i+1]==q[i+5]&&q[i+4]=="A") { r+=i+1+" "+i+" "; }
}
if(q[i+1]=="A"&&COL[i]<2){ //處理右二棋子
switch(QZLX[q[i+2]]){
case "H": { r+=i+2+" "+i+" "; break; }
case "B": { r+=i+2+" "+i+" "; }
}
}
if(QZLX[q[i-3]]=="B"&&(q[i+1]=="A"||q[i-4]=="A")) { r+=i-3+" "+i+" "; } //右上方棋子
if(QZLX[q[i+5]]=="B"&&(q[i+1]=="A"||q[i+4]=="A")) { r+=i+5+" "+i+" "; } //右下方棋子
}
}
return q.join(" ")+" "+r; //為防止對象過多,干脆用一個單串返回
}
function zb(q,s,d){
var c=q[s];
switch(QZLX[c]){
case "B": {q[s]="A"; q[d]=c; break; }
case "C": {q[s]=q[s+4]="A"; q[d]=q[d+4]=c; break; }
case "H": {q[s]=q[s+1]="A"; q[d]=q[d+1]=c; break; }
case "M": {q[s]=q[s+1]=q[s+4]=q[s+5]="A"; q[d]=q[d+1]=q[d+4]=q[d+5]=c; break; }
}
return q;
}
//------------------------------------
function ZBD(){ //構造走步隊對象
this.z=Array(); //隊列,this為當前對象,常在構造時使用,在沒有用new分配一個實體前,this不明確
this.hs=Array(); //回朔指針
this.hsb=Array(); //回朔步
this.hd=0; //隊頭指針
this.cur=Array();//隊頭信息
this.Rd=zbrd; //入隊方法
this.Cd=zbcd; //出隊方法
this.getQP=getqp;
this.cur.n="null"; //cur無內容標記
}
function zbrd(q,fla){ //走步入隊,第二個參數(shù)為是否回朔
var n=this.z.length;
this.z[n]=zbFX(q);
if(fla==-1) this.hs[n]=0,this.hsb[n]="無棋子";//回朔指針
else this.hs[n]=this.hd,this.hsb[n]=this.cur[this.cur[this.cur.p-2]];
}
function zbcd(){ //走步出隊
if(this.cur.n=="null"){
this.cur=this.z[this.hd].split(" ");
this.cur.n=this.cur.length-1;//原串中最后一個是空格所以多減1
this.cur.p=20; //棋步游標
}
if(this.cur.p>=this.cur.n) {this.hd++; this.cur.n="null"; return "";}
var p=this.cur.p;
this.cur.p+=2;
if(this.cur[this.cur[p]]==this.hsb[this.hd]) return "";
return zb(this.cur.slice(0,20),this.cur[p]-0,this.cur[p+1]-0); //使用拷貝盤傳入
}
function getqp(n){ //從隊中取出棋盤
var s=this.z[n].split(" ");
return s.slice(0,20);
}
//------------------------------------
//廣度優(yōu)先搜索
//------------------------------------
function GDsearch(q,dep){ //參數(shù)為棋盤及搜索最大深度
var i,k,ok=0,bm,v; //ok表示是否找到
var js=0,js2=0;
var D=new ZBD(); //建立走步隊
var JD=Array(); //結點記錄器
for(D.Rd(q,-1),i=1;i<=dep&&!ok;i++){ //一層一層的搜索
k=D.z.length;
while(D.hd<k){ //廣度優(yōu)先
q=D.Cd(); //出隊
if(q=="") continue; //返回空說明是步集出隊,不是步出隊
if(q[17]=="M"&&q[18]=="M") { ok=1;break;} //大王出來了
if(i==dep) continue; //到了最后一層就不再入隊了
bm=BM(q); v=JD[bm];
js++;
if(!v){
js2++ ; //js搜索總次數(shù)計數(shù)和js2遍歷的實結點個數(shù)
JD[bm]=i, JD[dcBM(q)]=i;//對節(jié)點及其對稱點編碼并計錄結點深度
D.Rd(q,0); //入隊
}
}
}
k=i-1; //實際計算的層數(shù)
var s="共遍歷"+js+"個節(jié)點,其中實結點"+js2+"搜索步數(shù)"+k+"<hr>";
var hs=Array();
if(ok){
for(i=1,hs[0]=D.hd;i<k;i++) hs[i]=D.hs[hs[i-1]]; //回塑
for(i=k-1;i>=0;i--) s+=qpToS(D.getQP(hs[i]))+"<hr>";
s+=qpToS(q);
}
else s+="此局"+dep+"步內無解";
return s;
}
document.write(GDsearch(qp,130));
</script>
</body>
</html>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -