迷宫问题-寻找最短路径

2019 精帖
0 380

迷宫问题-寻找最短路径

算法:广度优先搜索

数据结构:队列,链表

QQ截图20190209002426.png

代码实现:

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


留言(0)
加载更多
猜你喜欢
  • blog centos7防火墙

    1、firewalld的基本使用启动: systemctl start firewalld关闭: systemctl stop firewalld查看状态: systemctl status firewalld 开机禁用 : system
  • blog 枚举算法案例--熄灯

    熄灯1.描述有一个有按钮组成的矩阵,其中每行有6个按钮,共5行。每个按钮的位置上有一盏灯。当按下一个按钮后,该按钮以及周围位置(上下左右)的灯都会改变一次。即(原来亮的变暗,原来暗的变亮)对矩阵中的每一盏灯设置一个初始状态。请你写一
  • blog 线程的同步

    多线程带来的: 线程有时候回和其他线程共享一些资源,比如内存、数据库等。当多个线程同时读写同一份共享资源的时候,可能会发生冲突。这时候,我们就需要引入线程“同步”机制,即各位线程之间要有顺序使用,不能杂乱无章随意使用。实例
  • blog 算法-求和

    描述 给定一个int类型一维数组 a[],和一个int类型的数值 b。编写一个程序,判断数组中有没有两个数(a[i],a[j])的和等于b,如果存在,返回两个数在a数组中的下表(return new int[]={1,2}
  • blog 数据结构-图的着色

    数据结构-图的着色描述: 图的m-着色判定——给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色法使G中任意相邻的2个顶点着不同颜色?个人感觉图的着色类似与八皇后
  • blog 汉诺塔

    汉诺塔:汉诺塔(Tower of Hanoi)源于印度传说中,大梵天创造世界时造了三根金钢石柱子,其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在
  • blog 温故01背包

    01背包是动态规划算法的一个经典例目: 在n种物品中选取若干件(每种物品只有一件只能选择一次) 放在空间为W的背包里,每种物品的体积为wigth[1],wigth[2],wigth[3],wigth[n], 与之相对应
  • ofc springboot跨域及其解决方案

    springboot跨域及其解决方案
  • ofc springboot集群session共享(springSession+redis+nginx)

    springboot集群session共享(springSession+redis+nginx)
  • blog 算法-渗透

    描述: 渗透,给一个n*m的矩阵,0为空白,1为白纸,2为墨水,墨水每经过每一秒会将上下左右相邻的白纸染成黑色,然后继续渗透,判断此图中的白纸终是否能够全部被墨水染上色,若能需要输出所有白纸全部被墨水染上色的时间。j