📄 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节点,哈希%d节点,队长%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){ //走步入队,第二个参数为是否回朔
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);
}
//------------------------------------
//广度优先搜索
//------------------------------------
function GDsearch(q,dep){ //参数为棋盘及搜索最大深度
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){ //广度优先
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搜索总次数计数和js2遍历的实结点个数
JD[bm]=i, JD[dcBM(q)]=i;//对节点及其对称点编码并计录结点深度
D.Rd(q,0); //入队
}
}
}
k=i-1; //实际计算的层数
var s="共遍历"+js+"个节点,其中实结点"+js2+"搜索步数"+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 + -