本学期上机看到机房有本《数据结构》，拿来翻了翻。发现有些问题以前都在思考怎么实现他，比如这次我说的“迷宫求解”问题。
原本问题是讲的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">
<!--
.STYLE1 {color: #FF0000}
.o{ background:#ffffff;}
.z{ background:#CCCCCC;}
.y{background-color:#FFFFCC;}
-->
</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>
</head>
<body>
迷宫尺寸：<input type="text" value="10" size="4" id="mg_size" />
<input type="button" value="生成迷宫" onclick="init_migong();" />
<input type="button" value="移动" onclick="move();" id="btnmove" />
<div id="migong"></div>
<div id="disp"></div>
<div id="path"></div>
<div id="progress"></div>
</body>
</html>