Java描述数据结构之迷宫问题

分手后的思念是犯贱 2022-05-25 05:25 193阅读 0赞

老鼠走迷宫是堆栈在实际应用中的一个很好例子。在实验中，老鼠被放在一个迷宫里，当老鼠走错路时就会重来一次并把走过的路记起来，避免重复走同样的路，就这样直到找到出口为止。下面使用二维数组来模拟迷宫地图，当某个方向的值为0时，表示可以走的路，为1时表示路两边的墙，利用链表来记录走过的位置，并将走过的位置的数组元素内容标识为2（如下图所示）：

![20180508202522658][]

程序源代码如下：

// =============== Program Description ===============
    // 程序名称： Maze.java                               
    // 程序目的：老鼠走迷宫
    // ===================================================
    import java.io.*;
    public class Maze
    {
    public static int ExitX= 8;			//定义出口的X坐标在第9行
    public static int ExitY= 10;		//定义出口的Y坐标在第11列 
    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,0,0,0,1,1},
    				  {1,1,1,0,1,1,0,1,1,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[]) throws IOException
       {
    	int i,j,x,y;
    	TraceRecord path=new TraceRecord();
    	x=1;	
    	y=1;   
    	System.out.print("[迷宫的路径(0的部分)]\n"); 
    	for(i=0;i<10;i++)
    	{
    		for(j=0;j<12;j++)
    			System.out.print(MAZE[i][j]);
    		System.out.print("\n");
    	}
    	while(x<=ExitX&&y<=ExitY)
    	{
    		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(chkExit(x,y,ExitX,ExitY)==1) 
    			break;
    		else
    		{
    			MAZE[x][y]=2;
    			path.delete();
    			x=path.last.x;
    			y=path.last.y;
    		}
    	}
    	System.out.print("[老鼠走过的路径(2的部分)]\n"); 
    	for(i=0;i<10;i++)
    	{
    		for(j=0;j<12;j++)
    			System.out.print(MAZE[i][j]);
    		System.out.print("\n");
    	}
       }
    
    public static int chkExit(int x,int y,int ex,int ey)
    {
    	if(x==ex&&y==ey)
    	{
    		if(MAZE[x-1][y]==1||MAZE[x+1][y]==1||MAZE[x][y-1] ==1||MAZE[x][y+1]==2)
    			return 1;
    		if(MAZE[x-1][y]==1||MAZE[x+1][y]==1||MAZE[x][y-1] ==2||MAZE[x][y+1]==1)
    			return 1;
    		if(MAZE[x-1][y]==1||MAZE[x+1][y]==2||MAZE[x][y-1] ==1||MAZE[x][y+1]==1)
    			return 1;
    		if(MAZE[x-1][y]==2||MAZE[x+1][y]==1||MAZE[x][y-1] ==1||MAZE[x][y+1]==1)
    			return 1;
        }
    	return 0;
    }
    }

// =============== Program Description ===============
    // 程序名称： TraceRecord.java                               
    // 程序目的：记录老鼠迷宫的行走路径
    // ===================================================
    
    class Node 
    {
    	int x;
    	int y;
    	Node next;
    	public Node(int x,int y)
    	{
    		this.x=x;
    		this.y=y;
    		this.next=null;
    	}
    }
    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=newNode;
    			last=newNode;
    		}
    		else
    		{
    			last.next=newNode;
    			last=newNode;
    		}
    	}
    
    	public void delete()
    	{
    		Node newNode;
    		if(this.isEmpty())
    		{
    			System.out.print("[队列已经空了]\n");
    			return;
    		}
    		newNode=first;
    		while(newNode.next!=last) 
    			newNode=newNode.next;
    		newNode.next=last.next;
    		last=newNode;
    
    	}
    }

[20180508202522658]: /images/20220525/0284c1a9c9dc4d059197dee53f03d75a.png