set.java

解迷宫的算法

package searchWay;
//import control.LinkStack;
//import control.BidirectLinkNode;
public class Set {
	private static LinkQueue s=new LinkQueue();

	/**
	 * @param args
	 */
	public static boolean MazePath(BidirectLinkNode[][] map,BidirectLinkNode start,BidirectLinkNode end){
		s.head.x=start.x;	
		s.head.y=start.y;	
		s.head.everstepped=start.everstepped;
		/*设置循环
		 * 当队的头节点指向出口时，打印走过的路径并返回true
		 * 如果头节点不是出口，就判断此点可否继续走下去
		 * 如果当前头节点是死路，就将队的头节点换为下一个节点
		 */
		do{
			if(s.head.x==end.x&&s.head.y==end.y){
				do{
				System.out.println("<"+s.head.x+","+s.head.y+">");
				s.head=s.head.fathernode;
				if(s.head.prior==s.headnode)	{System.out.print("<"+s.head.x+","+s.head.y+">"+"\n");}
				}while(!(s.head.prior==s.headnode));
				return true;
			}

			else {if(Cango(s.head,map)){	//调用Cango函数判断地图map当前点s.head周围八个方向若有路可走时
					for(int i=0;i<8;i++){	//这层循环是将当前点周围可通行的点进队,并将进队的点的父节点设为当前节点
						switch(i){			//若周围某点可通行，就将它的父节点设为当前的头节点，再将它入队，最后在地图上将此点设为已经走过的点
						case 0:if(!map[s.head.x-1][s.head.y+1].everstepped)  	{map[s.head.x-1][s.head.y+1].fathernode=s.head;	s.push(map[s.head.x-1][s.head.y+1]);	map[s.head.x-1][s.head.y+1].everstepped=true;};
						case 1:if(!map[s.head.x][s.head.y+1].everstepped) 		{map[s.head.x][s.head.y+1].fathernode=s.head;	s.push(map[s.head.x][s.head.y+1]);		map[s.head.x][s.head.y+1].everstepped=true;};
						case 2:if(!map[s.head.x+1][s.head.y+1].everstepped)		{map[s.head.x+1][s.head.y+1].fathernode=s.head;	s.push(map[s.head.x+1][s.head.y+1]);	map[s.head.x+1][s.head.y+1].everstepped=true;};
						case 3:if(!map[s.head.x+1][s.head.y].everstepped) 		{map[s.head.x+1][s.head.y].fathernode=s.head;	s.push(map[s.head.x+1][s.head.y]);		map[s.head.x+1][s.head.y].everstepped=true;};
						case 4:if(!map[s.head.x+1][s.head.y-1].everstepped) 	{map[s.head.x+1][s.head.y-1].fathernode=s.head;	s.push(map[s.head.x+1][s.head.y-1]);	map[s.head.x+1][s.head.y-1].everstepped=true;};
						case 5:if(!map[s.head.x][s.head.y-1].everstepped) 		{map[s.head.x][s.head.y-1].fathernode=s.head;	s.push(map[s.head.x][s.head.y-1]);		map[s.head.x][s.head.y-1].everstepped=true;};
						case 6:if(!map[s.head.x-1][s.head.y-1].everstepped) 	{map[s.head.x-1][s.head.y-1].fathernode=s.head;	s.push(map[s.head.x-1][s.head.y-1]);	map[s.head.x-1][s.head.y-1].everstepped=true;};
						case 7:if(!map[s.head.x-1][s.head.y].everstepped) 		{map[s.head.x-1][s.head.y].fathernode=s.head;	s.push(map[s.head.x-1][s.head.y]);		map[s.head.x-1][s.head.y].everstepped=true;};
						}//switch
					}//for
					s.head=s.head.next;
				}//else
			else s.head=s.head.next;	//若当前点周围无路可进，则察看队中的下一点
			}
		}while(!s.empty());
		return false;
	}
	
	//判断地图一点p周围八个方向有无可走的点
	public static boolean Cango(BidirectLinkNode p,BidirectLinkNode[][] map){
		int m,n;
		m=p.x;	n=p.y;
		//只要有一个点能走，就返回true
		return !(!map[m-1][n+1].everstepped)||(!map[m][n+1].everstepped)||(!map[m+1][n+1].everstepped)||(!map[m+1][n].everstepped)||(!map[m+1][n-1].everstepped)||(!map[m][n-1].everstepped)||(!map[m-1][n-1].everstepped)||(!map[m-1][n].everstepped);	
	}
	

	/*制作地图
	 *整型二维数组的地图作为参数，帮助建立双向链节点二维数组的地图。
	 *当整型数组的某一元素值为1时，相应的节点数组的元素被定义成“已经走过的点”，既是障碍
	*/
	static BidirectLinkNode[][] CreatMap(int[][] map){
		BidirectLinkNode[][] m=new BidirectLinkNode[12][12];
		for(int x=0;x<12;x++){
			for(int y=0;y<12;y++){
				if(map[x][y]==1) m[x][y]=new BidirectLinkNode(x,y,true);
				else m[x][y]=new BidirectLinkNode(x,y,false);
			}
		}
		return m;
	}
	
	
	
	public static void main(String[] args) {
		
	    int[][] m={{1,1,1,1,1,1,1,1,1,1,1,1},
					{1,0,0,1,1,0,0,1,1,1,1,1},
				  	{1,0,1,1,1,1,1,1,0,0,0,1},
				  	{1,0,0,0,1,0,0,1,0,1,1,1},
				  	{1,0,1,1,0,1,1,0,0,0,1,1},
				  	{1,0,1,0,1,0,1,0,1,0,1,1},
				  	{1,1,0,1,0,1,0,0,1,1,0,1},
				  	{1,0,1,1,1,0,1,1,1,1,0,1},
				  	{1,1,0,0,1,0,1,1,1,0,1,1},
				  	{1,0,1,1,1,0,0,1,0,1,1,1},
				  	{1,0,0,0,0,1,0,1,0,0,0,1},
				  	{1,1,1,1,1,1,1,1,1,1,1,1} };
	    
	    BidirectLinkNode[][] map=CreatMap(m);	//制作地图
		
		BidirectLinkNode start=new BidirectLinkNode(1,1,true);//分别为当前点、起点、终点
		BidirectLinkNode end =new BidirectLinkNode(1,5);

		//若有最短路径则打印此路径
	if(MazePath(map,start,end))System.out.println("以上是最短路径");
	else System.out.println("此迷宫无通路");
	}

}