算法：广度优先搜索
数据结构：队列，链表
代码实现：
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title></title>
<script>
var flag=true;
window.onload = function() {
var wid=20;
var box = document.getElementById('box');
var top = 0;
for(i = 0; i < wid; i++) {//初始化地图
var left = 0;
for(j = 0; j < wid; j++) {
var odiv = document.createElement('div');
odiv.className = 'odiv';
odiv.style.top = top + 'px';
odiv.style.left = left + 'px';
odiv.setAttribute("state","1");
//odiv.innerHTML=(i+1)+"-"+(j+1);
odiv.setAttribute("id",(i+1)+"-"+(j+1));
box.appendChild(odiv);
left += 31;
}
top += 31;
}
function Node(i, j, n) { //节点信息
this.i = i;//
this.j = j;//自身节点位置坐标
this.n=n;//记录父节点
}
function ArrayQueue(){ //队列
var arr = [];
this.push = function(element){ //入队
arr.push(element);
return true;
}
this.pop = function(){ //出队
return arr.shift();
}
this.size = function(){ //队列长度
return arr.length;
}
}
var mark = new Array(); //初始化地图标记信息
function remark(){
for(var x = 0; x < (wid+2); x++) {
mark[x] = new Array(); //
for(var y = 0; y < (wid+2); y++) {
mark[x][y] = 0; //数组初始化为0
}
}
}
remark();
//方位增量
var move = [
[0, 0],
[0, 1],
[1, 0],
[0, -1],
[-1, 0]
];
var maze = [//初始化地图信息
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,1,1,1,1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,1,1],
[1,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1],
[1,0,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1],
[1,0,1,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1],
[1,0,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1],
[1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1],
[1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1],
[1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1],
[1,0,1,0,0,1,0,1,0,0,0,1,0,1,0,1,0,0,1,0,1,1],
[1,0,1,0,0,1,0,1,1,1,1,1,0,1,0,1,0,0,1,0,1,1],
[1,0,1,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,1,0,1,1],
[1,0,1,0,0,1,1,1,1,1,0,1,0,1,0,1,0,0,1,0,1,1],
[1,0,1,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0,1,0,1,1],
[1,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,0,0,1,0,1,1],
[1,1,1,1,1,1,1,0,0,1,1,0,0,1,1,0,0,0,1,0,1,1],
[1,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,1,1,1,0,1,1],
[1,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,1,0,1,1],
[1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,1,1],
[1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]];
var interval;
var f=false;
function mazes(){
var q=new ArrayQueue();
q.push(new Node(1,1,null));
var n;
interval = window.setInterval(function() {
n=q.pop();
//console.log(n);//访问元素
document.getElementById(n.i+"-"+n.j).style.background="greenyellow";
if(n.i==wid&&n.j==wid){
console.log(n);
var p=n;
f=true;
while(p!=null){
document.getElementById(p.i+"-"+p.j).style.background="green";
p=p.n;
}
clearInterval(interval);
}
for(var v=1;v<=4;v++){
var g = n.i+move[v][0],
h = n.j+move[v][1];
if(maze[g][h] == 0 && mark[g][h] == 0){
q.push(new Node(g,h,n));
mark[g][h]=1;
}
}
if(q.size()<=0){
if(!f){
console.log("没有找到出口");
alert("没有找到出口");
clearInterval(interval);
}
}
},50);
}
//初始化地图背景
function draw(){
for(q=1;q<=20;q++){
for(w=1;w<=20;w++){
if(maze[q][w]==1){
document.getElementById(q+"-"+w).style.background="#aaa";
document.getElementById(q+"-"+w).setAttribute("state","1");
}else{
document.getElementById(q+"-"+w).style.background="#eee";
document.getElementById(q+"-"+w).setAttribute("state","0");
}
}
}
}
draw();
function begin(){
if(flag){
mazes();
flag=false;
}else{
alert("请重新绘制地图");
}
}
//从新绘制地图
function clear(){
clearInterval(interval);
remark();
draw();
flag=true;
}
//调整地图局部
function odivclick(){
var ij=this.getAttribute("id");
var arr=ij.split("-");
if(maze[parseInt(arr[0])][parseInt(arr[1])]==0){
maze[parseInt(arr[0])][parseInt(arr[1])]=1;
}else{
maze[parseInt(arr[0])][parseInt(arr[1])]=0;
}
clear();
}
document.getElementById("begin").onclick = begin;
document.getElementById("clear").onclick = clear;
//单元格添加点击事件
var list=document.getElementsByClassName('odiv');
for(var i in list) {
list[i].onclick=odivclick;
}
}
</script>
<style>
.odiv {
width: 30px;
height: 30px;
background: #aaa;
position: absolute;
font-size: 5px;
text-align: center;
line-height: 30px;
}
#box {
width: 620px;
height: 620px;
position: relative;
float: left;
border: 3px solid red;
}
#sss{
width: 1000px;
height: 500px;
float: left;
}
</style>
</head>
<body>
<div id="box">
</div>
<input type="button" value="开始寻找出口" id="begin" />
<input type="button" value="从新绘制地图" id="clear" />
</body>
</html>