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;
		/*設(shè)置循環(huán)
		 * 當(dāng)隊的頭節(jié)點(diǎn)指向出口時，打印走過的路徑并返回true
		 * 如果頭節(jié)點(diǎn)不是出口，就判斷此點(diǎn)可否繼續(xù)走下去
		 * 如果當(dāng)前頭節(jié)點(diǎn)是死路，就將隊的頭節(jié)點(diǎn)換為下一個節(jié)點(diǎn)
		 */
		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)){	//調(diào)用Cango函數(shù)判斷地圖map當(dāng)前點(diǎn)s.head周圍八個方向若有路可走時
					for(int i=0;i<8;i++){	//這層循環(huán)是將當(dāng)前點(diǎn)周圍可通行的點(diǎn)進(jìn)隊,并將進(jìn)隊的點(diǎn)的父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)
						switch(i){			//若周圍某點(diǎn)可通行，就將它的父節(jié)點(diǎn)設(shè)為當(dāng)前的頭節(jié)點(diǎn)，再將它入隊，最后在地圖上將此點(diǎn)設(shè)為已經(jīng)走過的點(diǎn)
						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;	//若當(dāng)前點(diǎn)周圍無路可進(jìn)，則察看隊中的下一點(diǎn)
			}
		}while(!s.empty());
		return false;
	}
	
	//判斷地圖一點(diǎn)p周圍八個方向有無可走的點(diǎn)
	public static boolean Cango(BidirectLinkNode p,BidirectLinkNode[][] map){
		int m,n;
		m=p.x;	n=p.y;
		//只要有一個點(diǎn)能走，就返回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);	
	}
	

	/*制作地圖
	 *整型二維數(shù)組的地圖作為參數(shù)，幫助建立雙向鏈節(jié)點(diǎn)二維數(shù)組的地圖。
	 *當(dāng)整型數(shù)組的某一元素值為1時，相應(yīng)的節(jié)點(diǎn)數(shù)組的元素被定義成“已經(jīng)走過的點(diǎn)”，既是障礙
	*/
	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);//分別為當(dāng)前點(diǎn)、起點(diǎn)、終點(diǎn)
		BidirectLinkNode end =new BidirectLinkNode(1,5);

		//若有最短路徑則打印此路徑
	if(MazePath(map,start,end))System.out.println("以上是最短路徑");
	else System.out.println("此迷宮無通路");
	}

}