maze.java

来自「已经编写好的数据结构课本程序可以减轻您的负担」· Java 代码 · 共 79 行

// =============== Program Description =============== 
// 程序名称： maze.java                                   
// 程序目的： 运用递归来解迷宫问题                     
// Written By Kuo-Yu Huang. (WANT Studio.)             
// =================================================== 
import ConsoleReader.*;					// 导入已定义的数据输入类

public class maze
{
	public static int Maze[][] = {		// 声明5*4的迷宫，外围不可走
				{1, 1, 1, 1, 1, 1, 1},
				{1, 0, 1, 0, 0, 0, 1},
				{1, 1, 0, 1, 1, 0, 1},
				{1, 1, 0, 1, 1, 0, 1},
				{1, 1, 1, 0, 1, 1, 1},
				{1, 0, 0, 1, 0, 1, 1},
				{1, 1, 1, 1, 0, 0, 1},
				{1, 1, 1, 1, 1, 1, 1} };
				
	public static void main (String args[])
	{
		int	i,j;			// 循环计数变量	

		System.out.println("==Problem of Maze ==");
		System.out.println("The Maze source is (1,1).");
		System.out.println("The Maze Destination is (6,5).");
		Way(1,1);

		System.out.println("The graph of Maze.");
		System.out.println("      0   1   2   3   4   5   6  ");
		System.out.println("    +---+---+---+---+---+---+---+");

		for (i=0;i<8;i++)
		{
			System.out.print(" "+i+" |");
			for (j=0;j<7;j++)
				System.out.print("-"+Maze[i][j]+"-|");
			System.out.println("");
			System.out.println("    +---+---+---+---+---+---+---+");
		}
	}		

// --------------------------------------------------- 
// 递归解迷宫问题                                      
// --------------------------------------------------- 
	public static boolean Way(int LocX,int LocY)
	{
		if ( Maze[6][5] == 2 )		// 递归结束条件 
			return true;
		else				// 递归执行部分 
			if ( Maze[LocY][LocX] == 0 )
			{
				Maze[LocY][LocX] = 2;
				if ( Way(LocX,LocY-1) )
					return true;
				else if ( Way(LocX+1,LocY-1) ) 
					return true;
				else if	( Way(LocX+1,LocY) ) 
					return true;
				else if ( Way(LocX+1,LocY+1) )
					return true;
				else if ( Way(LocX,LocY+1) )
					return true;
				else if ( Way(LocX-1,LocY+1) )
					return true;
				else if ( Way(LocX-1,LocY) )
					return true;
				else if	( Way(LocX-1,LocY-1) )
					return true;
				else
				{
					Maze[LocY][LocX] = 3;
					return false;
				}
			}
			else
				return false;
	}
}