【问题描述】
以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
（1）根据二维数组，输出迷宫的图形。
（2）探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，输出从入口到出口的行走路径。
【算法分析】
主要考查数据结构-栈。栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
详细请看百度百科： http://baike.baidu.com/subview/38877/12246229.htm?fr=aladdin
【实现分析】
可使用回溯方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
【代码展示】
1.首先创建一个Point类：
package com.albertshao.study;
public class Point {
private int x;
private int y;
public Point() {
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "Point [x=" + x + ", y=" + y + "]";
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
迷宫类：
package com.albertshao.study;
import java.util.Scanner;
import java.util.Stack;
public class Maze {
int maze[][];
private int row = 3;
private int col = 3;
Stack<Point> stack;
boolean p[][] = null;
public Maze() {
maze = new int[15][15];
stack = new Stack<Point>();
p = new boolean[15][15];
}
/* 更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
* construct the maze
*/
public void init() {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入迷宫的行数");
row = scanner.nextInt();
System.out.println("请输入迷宫的列数");
col = scanner.nextInt();
System.out.println("请输入" + row + "行" + col + "列的迷宫");
int temp = 0;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
temp = scanner.nextInt();
maze[i][j] = temp;
p[i][j] = false;
}
}
}
/*
* list, decide whether there is a road.
*/
public void findPath() {
int temp[][] = new int[row + 2][col + 2];
for (int i = 0; i < row + 2; ++i) {
for (int j = 0; j < col + 2; ++j) {
temp[0][j] = 1;
temp[row + 1][j] = 1;
temp[i][0] = temp[i][col + 1] = 1;
}
}
for(int i = 0; i < row + 2; i ++)
{
for(int j = 0; j < col + 2; j ++)
{
System.out.print(temp[i][j] + " ");
}
System.out.println();
}
// copy the original maze to the new temp.
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
temp[i + 1][j + 1] = maze[i][j];
}
}
System.out.println("after copying data");
for(int i = 0; i < row + 2; i ++)
{
for(int j = 0; j < col + 2; j ++)
{
System.out.print(temp[i][j] + " ");
}
System.out.println();
}
//from up-left to skip in the clockWise direction
int i = 1;
int j = 1;
p[i][j] = true;
stack.push(new Point(i, j));
while (!stack.empty() && (!(i == (row) && (j == col)))) {
if ((temp[i][j + 1] == 0) && (p[i][j + 1] == false)) { //turn right
p[i][j + 1] = true;
stack.push(new Point(i, j + 1));
j++;
} else if ((temp[i + 1][j] == 0) && (p[i + 1][j] == false)) { // turn down
p[i + 1][j] = true;
stack.push(new Point(i + 1, j));
i++;
} else if ((temp[i][j - 1] == 0) && (p[i][j - 1] == false)) { // turn left
p[i][j - 1] = true;
stack.push(new Point(i, j - 1));
j--;
} else if ((temp[i - 1][j] == 0) && (p[i - 1][j] == false)) { // turn up
p[i - 1][j] = true;
stack.push(new Point(i - 1, j));
i--;
} else {
stack.pop();
if (stack.empty()) {
break;
}
i = stack.peek().getX();
j = stack.peek().getY();
}
}
Stack<Point> newPos = new Stack<Point>();
if (stack.empty()) {
System.out.println("没有路径");
} else {
System.out.println("有路径");
System.out.println("路径如下：");
while (!stack.empty()) {
Point pos = new Point();
pos = stack.pop();
System.out.print("("+pos.getX() + "," + pos.getY()+") ");
newPos.push(pos);
}
}
/*
* print the path
*/
String resault[][] = new String[row + 1][col + 1];
for (int k = 0; k < row; ++k) {
for (int t = 0; t < col; ++t) {
resault[k][t] = (maze[k][t]) + "";
}
}
while (!newPos.empty()) {
Point p1 = newPos.pop();
resault[p1.getX() - 1][p1.getY() - 1] = "#";
}
for (int k = 0; k < row; ++k) {
for (int t = 0; t < col; ++t) {
System.out.print(resault[k][t] + "\t");
}
System.out.println();
}
}
public static void main(String []args)
{
Maze maze = new Maze();
maze.init();
maze.findPath();
}
}
测试结果：
请输入迷宫的行数 3 请输入迷宫的列数 3 请输入3行3列的迷宫 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 after copying data 1 1 1 1 1 1 0 1 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 有路径 路径如下： (3,3) (3,2) (2,2) (2,1) (1,1) # 1 0 # # 1 1 # #
备注:部分代码借鉴于网友。
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， scanner
， close() scanner java
， 迷宫
， stack
， system
， public
， temp
， 迷宫路径输出问题
， scanner string
， for数据int
数据结构 迷宫问题
用栈实现迷宫问题、c 用栈实现迷宫问题、搜索算法实现迷宫问题、mfc 实现迷宫小游戏、走迷宫游戏的java实现，以便于您获取更多的相关知识。
