~~~
/**
* 1 從maze.txt讀入迷宮
* 2 從入口坐標(biāo)(1,1)尋找到出口的通路
* 3 顯示迷宮中數(shù)據(jù)
* 0 退出程序
* MazeApp
* 創(chuàng)建人:guxiaohao
* 時(shí)間：2017年10月29日-上午9:56:52
* @version 1.0.0
*
*/
public class MazeApp {
// 程序菜單
static void menu() {
System.out.println("\t***********迷宮問(wèn)題*****************");
System.out.println("\t*? 1 從maze.txt讀入迷宮? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? *");
System.out.println("\t*? 2 從入口坐標(biāo)(1,1)尋找到出口的通路? *");
System.out.println("\t*? 3 顯示迷宮中數(shù)據(jù)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? *");
System.out.println("\t*? 0 退出程序? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? *");
System.out.println("\t***********************************");
System.out.println("\t請(qǐng)輸入菜單項(xiàng)：");
}
//程序入口
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();// 輸入菜單選項(xiàng)
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; // 不能重復(fù)求迷宮路徑，除非再次加載迷宮數(shù)據(jù)。
} else {
System.out.println("先執(zhí)行菜單1砂心，加載或再次加載迷宮數(shù)據(jù)雌团！");
}
break;
case 3:
if (maze != null) {
// 顯示迷宮的內(nèi)容（包括圍欄）期奔，*代表可通，#代表不通
printMaze(maze);
} else {
System.out.println("尚未加載迷宮數(shù)據(jù)制市！");
}
break;
case 0:
sc.close();
System.exit(0);
break;
default:
System.out.println("菜單選擇錯(cuò)誤志衍，請(qǐng)重新輸入!\n");
}
}
}
// 定義描述迷宮中當(dāng)前位置的類(lèi)
class T {
int x; // x代表當(dāng)前位置的行坐標(biāo)
int y; // y代表當(dāng)前位置的列坐標(biāo)
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; // 定義二維數(shù)組存取迷宮
int rowNum = 0, colNum = 0;
}
// 從文件中加載（讀鹊枧！）迷宮數(shù)據(jù)
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(" "); // 先讀入迷宮的行數(shù)和列數(shù)
maze.rowNum = Integer.parseInt(rc[0]);
maze.colNum = Integer.parseInt(rc[1]);
maze.mat = new char[maze.rowNum][]; // 存儲(chǔ)迷宮數(shù)據(jù)的二維數(shù)組
for (int i = 0; i < maze.rowNum; i++) {
// 每次讀入迷宮數(shù)據(jù)的一行淹辞，并轉(zhuǎn)換成char類(lèi)型的數(shù)組
maze.mat[i] = br.readLine().trim().toCharArray();
if (maze.mat[i].length != maze.colNum) {
System.out.println("數(shù)據(jù)文件中的迷宮行列數(shù)有誤医舆，請(qǐng)檢查數(shù)據(jù)文件!");
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("迷宮數(shù)據(jù)加載成功!");
return maze; // 返回迷宮對(duì)象
}
/**
* 搜索從左上角到右下角的迷宮通道
* 定義一個(gè)標(biāo)志數(shù)組mark[][],用來(lái)標(biāo)記走過(guò)的路徑,并全部賦初值為0(表示未走過(guò)),每走過(guò)一個(gè)坐標(biāo),就記當(dāng)前標(biāo)記為1
* app
* 方法名：searchMazePath
* 創(chuàng)建人：guxiaohao
* 時(shí)間：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();//每次循環(huán)把棧頂元素給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) {
// 定義一個(gè)棧，按從出口到入口依次進(jìn)棧象缀，出棧輸出即可得到路徑
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的棧頂時(shí)目標(biāo)蔬将，所以先把s中的結(jié)點(diǎn)全部導(dǎo)入到t
while (!s.isEmpty())
t.push(s.pop());
System.out.println("迷宮中的通道路徑為：");
// 輸出路徑，包括行坐標(biāo)央星，列坐標(biāo)霞怀，下一個(gè)位置方向
while (!t.isEmpty()) { // 棧非空，繼續(xù)輸出
T tmp = (T) t.pop();
System.out.print("（" + tmp.x + "莉给，" + tmp.y + "毙石，");// 輸出行坐標(biāo)，列坐標(biāo)
switch (tmp.dir) // 輸出相應(yīng)的方向
{
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;
}
}
}
// 顯示加載的迷宮內(nèi)容（包括四周的圍欄）颓遏，*代表可通徐矩，#代表不通
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();
}
}
}
~~~
