迷宫问题
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title></title>
<script>
var flag=true;
window.onload = function() {
var width = 20;
var box = document.getElementById('box');
var top = 0;
for(i = 0; i < width; i++) {//初始化地图
var left = 0;
for(j = 0; j < width; 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;
}
//方位增量
var move = [
[0, 0],
[0, 1],
[1, 0],
[0, -1],
[-1, 0]
];
var mark = new Array(); //初始化地图标记信息
function remark(){
for(var x = 0; x < 22; x++) {
mark[x] = new Array(); //
for(var y = 0; y < 22; y++) {
mark[x][y] = 0; //数组初始化为0
}
}
}
remark();
//初始化地图信息
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,1,1,0,1,1,0,0,0,0,0,1,0,0,1,0,0,0,1,1],
[1,1,0,0,0,0,0,1,0,1,0,1,0,0,1,0,0,0,1,0,0,1],
[1,0,0,1,0,1,1,0,0,0,1,0,0,1,0,0,1,0,1,1,0,1],
[1,1,0,0,1,1,0,1,1,0,1,0,0,1,0,1,0,1,0,0,0,1],
[1,0,0,1,0,0,0,0,1,0,1,0,1,0,1,0,0,1,0,1,1,1],
[1,1,0,0,0,1,0,1,1,0,1,0,0,0,1,0,1,1,0,0,0,1],
[1,0,1,1,1,1,0,1,0,0,0,1,1,0,1,0,0,0,1,1,0,1],
[1,0,1,0,0,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1],
[1,0,0,0,1,1,1,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1],
[1,1,0,1,1,0,0,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1],
[1,1,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,1,0,1],
[1,0,1,0,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1],
[1,0,0,1,0,0,1,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1],
[1,1,0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,1,0,1],
[1,0,1,0,0,0,0,1,1,0,1,0,1,0,0,1,1,0,1,0,0,1],
[1,1,0,0,1,0,1,0,0,1,0,0,0,1,1,0,0,0,0,1,0,1],
[1,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,1,0,1,1,0,1],
[1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1],
[1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,1,1,1],
[1,0,1,0,0,0,1,0,0,0,1,1,0,0,0,0,1,1,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]
];
function Node(i, j, v) { //节点信息
this.i = i;
this.j = j;
this.v = v;
}
function Stack() { //栈
this.dataStore = [];
this.top = 0;
}
Stack.prototype = {//定义栈的方法
pop: function() {
//出栈时，主要使用前减运算，返回栈顶元素，元素个数减一
return this.dataStore[--this.top];
},
push: function(elem) {
//入栈时，使用后加运算符，先在栈顶添加元素，元素个数加一
this.dataStore[this.top++] = elem;
},
peek: function() {
return this.dataStore[this.top - 1];
}
}
var interval;
//寻路关键算法（试探）
function mazes() {
//栈，用于保存走每一步的信息，包括每一步的坐标和方向
var stack = new Stack();
var s = new Node(1, 1, 1);
mark[1][1] = 1;
interval = window.setInterval(function() {
var g = s.i + move[s.v][0],
h = s.j + move[s.v][1];
if((g == 20 && h == 20) && maze[20][20] == 0) { //找到出口
console.log("找到出口")
var s_ = new Stack();
stack.push(s);
while(stack.top > 0) {
s_.push(stack.pop());
}
while(s_.top > 0) {
var l = s_.pop();
console.log("坐标：" + l.i + "-" + l.j);
}
clearInterval(interval);
alert("找到出口")
return;
}
if(maze[g][h] == 0 && mark[g][h] == 0) { //可以向前走
console.log(g+"-"+h);
document.getElementById(g+"-"+h).style.background="greenyellow";
mark[g][h] = 1;
stack.push(s);
s = new Node(g, h, 1);
} else if(s.v < 4) { //换个方向试探
s.v++;
} else { //无路可走，返回一步，从栈中取出记录的数据
if(s.v==4){
s.v++;
}
while(s.v == 5 && stack.top > 0) {
document.getElementById(s.i+"-"+s.j).style.background="#eee";
//mark[s.i][s.j]=0;//如果加这句，代表遍历所有的节点
s = stack.pop();
s.v++;
}
}
if((stack.top <= 0 && s.v >= 4)) {
console.log("没有找到出口")
alert("没有找到出口");
clearInterval(interval);
}
},20);
}
//初始化地图背景
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");
}
}
}
//开始寻找路径
function begin(){
if(flag){
mazes();
flag=false;
}else{
alert("请重新绘制地图");
}
}
//从新绘制地图
function clear(){
clearInterval(interval);
remark();
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");
}
}
}
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;
}
console.log(maze)
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;
}
</style>
</head>
<body>
<div id="box">
</div>
<input type="button" value="开始寻找出口" id="begin" />
<input type="button" value="从新绘制地图" id="clear" />
</body>
</html>
