~~~
/**
* 1 从maze.txt读入迷宫
* 2 从入口坐标(1,1)寻找到出口的通路
* 3 显示迷宫中数据
* 0 退出程序
* MazeApp
* 创建人:guxiaohao
* 时间：2017年10月29日-上午9:56:52
* @version 1.0.0
*
*/
public class MazeApp {
// 程序菜单
static void menu() {
System.out.println("\t***********迷宫问题*****************");
System.out.println("\t* 1 从maze.txt读入迷宫 *");
System.out.println("\t* 2 从入口坐标(1,1)寻找到出口的通路 *");
System.out.println("\t* 3 显示迷宫中数据 *");
System.out.println("\t* 0 退出程序 *");
System.out.println("\t***********************************");
System.out.println("\t请输入菜单项：");
}
//程序入口
public static void main(String[] args) {
Maze maze = null;
int choice;
boolean flag = false;
MazeApp md = new MazeApp();
Scanner sc = null;
sc = new Scanner(System.in);
while (true) {
menu();// 显示菜单
choice = sc.nextInt();// 输入菜单选项
switch (choice) {
case 1:
// 读取迷宫信息
maze = md.loadMaze();
flag = true; // 可以求迷宫路径了
break;
case 2:
if (maze != null && flag) {
// 求迷宫入口到出口的路径
if (!md.searchMazePath(maze))
System.out.println("迷宫中从（1,1）到（" + (maze.rowNum - 2)
+ "," + (maze.colNum - 2) + "）不存在通路!");
flag = false; // 不能重复求迷宫路径，除非再次加载迷宫数据。
} else {
System.out.println("先执行菜单1，加载或再次加载迷宫数据！");
}
break;
case 3:
if (maze != null) {
// 显示迷宫的内容（包括围栏），*代表可通，#代表不通
printMaze(maze);
} else {
System.out.println("尚未加载迷宫数据！");
}
break;
case 0:
sc.close();
System.exit(0);
break;
default:
System.out.println("菜单选择错误，请重新输入!\n");
}
}
}
// 定义描述迷宫中当前位置的类
class T {
int x; // x代表当前位置的行坐标
int y; // y代表当前位置的列坐标
int dir; // 0——东；1——南；2——西；3——北；4——不通
T() {
this.x = 1;
this.y = 1;
this.dir = 0;
}
T(int x, int y, int dir) {
this.x = x;
this.y = y;
this.dir = dir;
}
}
class Maze {
char mat[][] = null; // 定义二维数组存取迷宫
int rowNum = 0, colNum = 0;
}
// 从文件中加载（读取）迷宫数据
private Maze loadMaze() {
Maze maze = new Maze();
BufferedReader br = null;
try {
br = new BufferedReader(new FileReader(new File("maze.txt")));
String rc[] = br.readLine().trim().split(" "); // 先读入迷宫的行数和列数
maze.rowNum = Integer.parseInt(rc[0]);
maze.colNum = Integer.parseInt(rc[1]);
maze.mat = new char[maze.rowNum][]; // 存储迷宫数据的二维数组
for (int i = 0; i < maze.rowNum; i++) {
// 每次读入迷宫数据的一行，并转换成char类型的数组
maze.mat[i] = br.readLine().trim().toCharArray();
if (maze.mat[i].length != maze.colNum) {
System.out.println("数据文件中的迷宫行列数有误，请检查数据文件!");
return null;
}
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
br.close();
} catch (IOException e) {
e.printStackTrace();
}
}
printMaze(maze);// 显示迷宫
System.out.println("迷宫数据加载成功!");
return maze; // 返回迷宫对象
}
/**
* 搜索从左上角到右下角的迷宫通道
* 定义一个标志数组mark[][],用来标记走过的路径,并全部赋初值为0(表示未走过),每走过一个坐标,就记当前标记为1
* app
* 方法名：searchMazePath
* 创建人：guxiaohao
* 时间：2017年10月29日-上午9:42:32
* @param maze
* @return boolean
* @exception
* @since 1.0.0
*/
private boolean searchMazePath(Maze maze) {
LinkedStack ls = new LinkedStack();
int mark[][] = new int[maze.rowNum-1][maze.colNum-1];
for ( int i=1;i<maze.rowNum-1;i++)
for ( int j=1;j<maze.colNum-1;j++)
mark[i][j]=0;
T t = new T();
int tX = 1;
int tY = 1;
ls.push(t);
while( !ls.isEmpty() ){
T mt = (T) ls.getTop();//每次循环把栈顶元素给mt
tX = mt.x;
tY = mt.y;
if ( tX==maze.rowNum-2 && tY==maze.colNum-2 ) {
mt.dir = 0;
break;
}
if ( maze.mat[tX][tY+1] == '*' && mark[tX][tY+1] == 0 ) { //东方
mt.dir = 0;
ls.push(new T(tX,tY+1,0));
mark[tX][tY+1] = 1;
} else if ( maze.mat[tX+1][tY] == '*' && mark[tX+1][tY] == 0 ) { //南方
mt.dir = 1;
ls.push(new T(tX+1,tY,1));
mark[tX+1][tY] = 1;
} else if ( maze.mat[tX][tY-1] == '*' && mark[tX][tY-1] == 0 ) { //西方
mt.dir = 2;
ls.push(new T(tX,tY-1,2));
mark[tX][tY-1] = 1;
} else if ( maze.mat[tX-1][tY] == '*' && mark[tX-1][tY] == 0 ) { //北方
mt.dir = 3;
ls.push(new T(tX-1,tY,3));
mark[tX-1][tY] = 1;
} else {
ls.pop();
maze.mat[tX][tY] = 'Y';
}
}
if ( ls.isEmpty() ){
return false;
} else {
printPath(maze, ls);
return true;
}
}
// 显示迷宫中的通路
private void printPath(Maze maze, LinkedStack s) {
// 定义一个栈，按从出口到入口依次进栈，出栈输出即可得到路径
LinkedStack t = new LinkedStack();
for (int i = 0; i < maze.rowNum; i++) {
maze.mat[i] = Arrays.copyOf(maze.mat[i], maze.mat[i].length);
}
// 由于s的栈顶时目标，所以先把s中的结点全部导入到t
while (!s.isEmpty())
t.push(s.pop());
System.out.println("迷宫中的通道路径为：");
// 输出路径，包括行坐标，列坐标，下一个位置方向
while (!t.isEmpty()) { // 栈非空，继续输出
T tmp = (T) t.pop();
System.out.print("（" + tmp.x + "，" + tmp.y + "，");// 输出行坐标，列坐标
switch (tmp.dir) // 输出相应的方向
{
case 0:
System.out.println("→）");
maze.mat[tmp.x][tmp.y] = '→';
break;
case 1:
System.out.println("↓）");
maze.mat[tmp.x][tmp.y] = '↓';
break;
case 2:
System.out.println("←）");
maze.mat[tmp.x][tmp.y] = '←';
break;
case 3:
System.out.println("↑）");
maze.mat[tmp.x][tmp.y] = '↑';
break;
}
}
}
// 显示加载的迷宫内容（包括四周的围栏），*代表可通，#代表不通
private static void printMaze(Maze maze) {
for (int i = 0; i < maze.rowNum; i++) {
for (int j = 0; j < maze.colNum; j++)
System.out.print(maze.mat[i][j]);
System.out.println();
}
}
}
~~~
