迷宫求解（js） - 雨风的个人网站（分享一些学习笔记）

雨风的个人网站（分享一些学习笔记）

青箬笠，绿蓑衣，细雨斜风不须归

WORKS

ARTICLE

迷宫求解（js） (2017/9/29 14:59:27)

分类：电脑网络 | 标签：迷宫求解 javascript

本学期上机看到机房有本《数据结构》，拿来翻了翻。发现有些问题以前都在思考怎么实现他，比如这次我说的“迷宫求解”问题。

原本问题是讲的6*8的二维空间，外面一圈是障碍，内部随机产生障碍这样的，从左上角出发，到达右下角，找到这样一条路径（并不是最优）。

这个题目其实很简单，就是从坐标1,1开始，通过探索其相邻的上下左右4个单元格（原题为8个，包括对角线），如果找到了，就给出提示达到终点，如果没有找到，则提示不存在这样的路径。

想了想，决定用javascript实现。主要是调试方便，适合网上演示。

首先，生成迷宫，这个很简单，2个for循环，加上dom对象的innerHTML属性即可生成。迷宫我用背景颜色来表示，白色是通路，灰色是障碍，通路和障碍的比例是7:3，用随机函数来确定。当前所在单元格用圆点表示。

迷宫生成后，需要使圆点从左上交移动到右下角。

则采用穷举回溯法来完成，遍历当前圆点的上下左右4个单元格，如果该单元格为通路、且不是已经经过的单元格，则该单元格可以移动。圆点按照右、下、上、左的顺序进行尝试移动，移动完成后，该圆点显示一个移动方向的箭头。

如果某圆点无法移动了，还需要回溯到上一单元格继续尝试。当前单元格用黄色背景表示该单元格无法到达下一单元格，下一次碰到这样的单元格就不再移动到此单元格。

全部代码如下：

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
<title>迷宫求解 - By yufeng</title>
<style type="text/css">

</style>
<script type="text/javascript" language="javascript">
var mg_size;//迷宫大小
var arrpath;//记录已经走过的路径，用于回滚
var currx;//当前表格的x坐标
var curry;//当前表格的y坐标
function init_migong(){
//函数作用：迷宫初始化
//内容：生成迷宫的表格，用背景灰色表示障碍（数组用1表示），白色背景表示通路(数组用0表示)。
//      第一个表格和最后一个表格不能设置障碍。
arrpath=new Array();
mg_size=document.getElementById("mg_size").value;
var thead="<table border='0' cellpadding='0' cellspacing='1' bgcolor='#000000'>";
var trow="";
var tcell="";
var ocount=0;
var zcount=0;
var cname;
for(i=1;i<=mg_size;i++){
  trow=trow+"<tr>"
  for(j=1;j<=mg_size;j++){
   var rndnumber=Math.random();
   if(i==1&&j==1||i==mg_size&&j==mg_size){
    cname="o";
    ocount++;
   }else{
    if(rndnumber<0.3){
     cname="z";
     zcount++;
    }else{
     cname="o";
     ocount++;
    }
   }
   if(i==1&&j==1){
    havedot="·";
   }else{
    havedot="";
   }
   tcell=tcell+"<td width='20' height='20' class='"+cname+"' id='cell"+i+''+j+"'>"+havedot+"</td>"
  }
  trow=trow+tcell+"</tr>";
  tcell="";
}
thead=thead+trow+"</table>";
currx=1;
curry=1;
document.getElementById("migong").innerHTML=thead;
document.getElementById("disp").innerText="黑格子："+zcount+";白格子："+ocount;
document.getElementById("btnmove"). disabled="";
document.getElementById("path").innerText="";
arrpath[0]="1 1";
}
function move(){
var nextx;//下一个单元格的x坐标
var nexty;//下一个y坐标
var nextcell;//下一个单元格
var ismoved;
ismoved=false;
//尝试的顺序是右、下、上、左
//首先尝试向右移动单元格
document.getElementById("path").innerText="序列："+arrpath.toString()+" 当前单元："+ currx+","+curry;
nextx=parseInt(currx);
nexty=parseInt(curry)+1;
document.getElementById("progress").innerText="尝试向右("+nextx+","+nexty+")移动：";
if(nexty<=mg_size){
  nextcell=document.getElementById("cell"+nextx+""+nexty);
  if(nextcell.className=="o"&&nextcell.innerText==""){//表示可以移动
   document.getElementById("cell"+currx+""+curry).innerText="→";
   nextcell.innerText="·";
   currx=nextx;
   curry=nexty;
   ismoved=true;
   document.getElementById("progress").innerText=document.getElementById("progress").innerText+"成功！";
  }else{
    document.getElementById("progress").innerText=document.getElementById("progress").innerText+"失败！";
  }
}
if(ismoved==false){
  //向右移动失败，尝试向下移动
  nextx=parseInt(currx)+1;
  nexty=parseInt(curry);
  document.getElementById("progress").innerText=document.getElementById("progress").innerText+" 尝试向下("+nextx+","+nexty+")移动：";
  if(nextx<=mg_size){
   nextcell=document.getElementById("cell"+nextx+""+nexty);
   if(nextcell.className=="o"&&nextcell.innerText==""){//表示可以移动
    document.getElementById("cell"+currx+""+curry).innerText="↓";
    nextcell.innerText="·";
    currx=nextx;
    curry=nexty;
    ismoved=true;
    document.getElementById("progress").innerText=document.getElementById("progress").innerText+"成功！";
   }else{
    document.getElementById("progress").innerText=document.getElementById("progress").innerText+"失败！";
   }
  }else{
   document.getElementById("progress").innerText=document.getElementById("progress").innerText+"失败1！";
  }
}
if(ismoved==false){
  //向下移动失败，尝试向上移动
  nextx=parseInt(currx)-1;
  nexty=parseInt(curry);
  document.getElementById("progress").innerText=document.getElementById("progress").innerText+" 尝试向上("+nextx+","+nexty+")移动：";
  if(nextx>0){
   nextcell=document.getElementById("cell"+nextx+""+nexty);
   if(nextcell.className=="o"&&nextcell.innerText==""){//表示可以移动
    document.getElementById("cell"+currx+""+curry).innerText="↑";
    nextcell.innerText="·";
    currx=nextx;
    curry=nexty;
    ismoved=true;
    document.getElementById("progress").innerText=document.getElementById("progress").innerText+"成功！";
   }else{
    document.getElementById("progress").innerText=document.getElementById("progress").innerText+"失败！";
   }
  }
}
if(ismoved==false){
  //向上移动失败，尝试向左移动
  nextx=parseInt(currx);
  nexty=parseInt(curry)-1;
  document.getElementById("progress").innerText=document.getElementById("progress").innerText+" 尝试向左("+nextx+","+nexty+")移动：";
  if(nexty>0){
   nextcell=document.getElementById("cell"+nextx+""+nexty);
   if(nextcell.className=="o"&&nextcell.innerText==""){//表示可以移动
    document.getElementById("cell"+currx+""+curry).innerText="←";
    nextcell.innerText="·";
    currx=nextx;
    curry=nexty;
    ismoved=true;
    document.getElementById("progress").innerText=document.getElementById("progress").innerText+"成功！";
   }else{
    document.getElementById("progress").innerText=document.getElementById("progress").innerText+"失败！";
   }
  }
}
//以上尝试都失败，则回滚
if(ismoved){
  arrpath.push(currx+" "+curry);
}else{
  document.getElementById("cell"+currx+""+curry).innerText="";
  document.getElementById("cell"+currx+""+curry).className="y";
  arrpath.pop(currx+" "+curry);
  if(arrpath.length==0){
   alert("can't reach the terminal!");
   document.getElementById("btnmove"). disabled="disable";
  }else{
   var lastitem;
   lastitem=getlastitem(arrpath);
   currx=getxy(lastitem,"x");
   curry=getxy(lastitem,"y");
  }
  //alert(currx+","+curry);
}
if(currx==mg_size&&curry==mg_size){
  alert("bingo! you reached the terminal!");
  document.getElementById("btnmove"). disabled="disable";
}
}
function getlastitem(parr){
var l=parr.length;
//alert(garr[l-1));
return parr[l-1];
}
function getxy(parr,xy){
var arrg=new Array();
arrg=parr.split(" ");
if(arrg.length==2){
  if(xy=="x"){
   return arrg[0];
  }else{
   return arrg[1];
  }
}
}
</script>