迷宫问题的研究与实现

迷宫问题的研究与实现2015-02-17【问题描述】

以一个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;}@Overridepublic 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];}/** 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 directionint 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 leftp[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 upp[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] + "	"）;}System.out.println（）;}}public static void main（String []args） {Maze maze = new Maze（）;maze.init（）;maze.findPath（）;}}

测试结果：

请输入迷宫的行数3请输入迷宫的列数3请输入3行3列的迷宫0 1 00 0 11 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 data1 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 # #

备注:部分代码借鉴于网友。

From：csdn博客风中静行