首页 > 代码库 > 利用队列解决迷宫问题
利用队列解决迷宫问题
首先定义节点的数据类型：
//定义节点的数据结构class Node{ int x; int y; Node next; public Node(int x,int y) { // TODO Auto-generated constructor stub this.x=x; this.y=y; this.next=null; }}建立一个记录轨迹的类，完成节点的插入与删除工作：
package com.gqx.maze;/** * 记录老鼠走迷宫的路径 * @author 郭庆兴 * */public class TraceRecord { public Node first; public Node last; public boolean isEmpty(){ return first==null; } public void insert(int x,int y){ Node newNode=new Node(x, y); if (this.isEmpty()) { first=last=newNode; }else { last.next=newNode; last=newNode; } } public void delete(){ Node newNode; if (this.isEmpty()) { System.out.println("队列已经空了！/n"); return; } newNode=first; while (newNode.next!=last) { newNode=newNode.next; } newNode.next=last.next; last=newNode; }}写一个主程序，在一个已知的迷宫中去完成路径的遍历（其中‘1’代表障碍物，‘0’代表道路可行，2代表老鼠的轨迹路线）：
package com.gqx.maze;public class MazeMain { //定义出口的坐标 private static int exit_X=8; private static int exit_Y=10; //声明迷宫数组 public static int[][] maze={{1,1,1,1,1,1,1,1,1,1,1,1}, {1,0,0,0,1,1,1,1,1,1,1,1}, {1,1,1,0,1,1,0,1,1,0,1,1}, {1,1,1,0,1,1,0,0,0,0,1,1}, {1,1,1,0,0,0,0,1,1,0,1,1}, {1,1,1,0,1,1,0,1,1,0,1,1}, {1,1,1,0,1,1,0,1,1,0,1,1}, {1,1,1,1,1,1,0,1,1,0,1,1}, {1,1,0,0,0,0,0,0,1,0,0,1}, {1,1,1,1,1,1,1,1,1,1,1,1} }; public static void main(String[] args) { // TODO Auto-generated method stub int i,j,x=1,y=1; TraceRecord path=new TraceRecord(); System.out.println("迷宫的地图如下："); for (i = 0; i < 10;i ++) { for (j = 0; j < 12 ;j++){ System.out.print(maze[i][j]); } System.out.println(); } while (x<=exit_X && y<=exit_Y) { maze[x][y]=2; if (maze[x-1][y]==0) { x-=1; path.insert(x, y); } else if (maze[x+1][y]==0) { x+=1; path.insert(x, y); } else if (maze[x][y-1]==0) { y-=1; path.insert(x, y); } else if (maze[x][y+1]==0) { y+=1; path.insert(x, y); } else if (x==exit_X && y==exit_Y) { break; } else { maze[x][y]=2; path.delete(); x=path.last.x; y=path.last.y; } } System.out.println("老鼠走过的路径是："); for (i = 0; i < 10; i++) { for (j = 0; j < 12; j++) { System.out.print(maze[i][j]); } System.out.println(); } }}运行结果如图：
利用队列解决迷宫问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。