迷宫问题-js实现

硅谷探秘者 2976 0 0


迷宫问题

image.png

<!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>


猜你喜欢
数据结构与算法 8392 -寻找最短路径算法:广度优先搜索数据结构:队列,链表代码:!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
数据结构与算法 7687 1.描述::上面有一个,灰色部分代表不能通过,白色部分代表可以通过,在从a点出发,能否找到一条路径到达b点,如果能,输出此路径。下面采用试探法求解,采用栈结构保存每一步的内容(包括坐标
数据结构与算法 8173 意的最短路径。遍历过程中需要一个数组记录遍历的过程,即经过一个节点时,需要记录下是从哪一个节点(或者是以什么方式)到达此节点的。然后利用这个过程关系,可以推出整个过程路径。代码:packagecl
前端(h5) 506 html纯js图片懒加载html纯js图片懒加载案例代码下载地址:http://www.jiajiajia.club/file/info/JA67P0
html图片懒加载 402 js图片懒加载lazyLoading.html测试页面
前端(h5) 1129 js(分钟:秒)倒计时varmaxtime=res.data.answerMsg.surplus;vartimer=setInterval(function(){if(maxtime=0
前端(h5) 1311 1.锚点定位很简单两行搞定:ahref="#anchorName"点击跳转到anchorName的位置/aaname="anchorName"anchorName/a2.js代码,并带滑动效果
游戏 算法 653 源码:packagewin;importjava.awt.EventQueue;importjava.util.Collections;importjava.util.HashMap;importjava.util.LinkedList;importjava.util.Map;importjavax.swing.JFrame;importjavax.swing.JPanel;importjavax
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16 2021年12月  14 2022年01月  6
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议
目录
祝愿神州十三飞行乘组平安归来