1.问题描述
用一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。编程实现选择任意通路作为入口和出口，探寻从迷宫入口到出口有无通路，若有，则求出一条从入口到出口的通路；若无则给出没有通路的结论信息。
2.要求
(1) 实现一个以链表作为存储结构的栈类。
(2) 利用栈设计一求解迷宫的非递归算法。
(3) 编写测试程序，求出迷宫通路，若无通路，则输出没有通路的提示信息；若有通路，则以三元组 ( i, j, d ) 的形式输出通路，其中，( i , j ) 指示迷宫中的一个位置坐标，d 表示走到下一坐标的方向（1、2、3、4 分别表示东、南、西、北4个方向）。
“穷举求解”
代码改编自《数据结构与算法简明教程》（Java语言版） -叶小平 陈瑛
import java.util.Scanner;public class Maze {public static void main(String[] args) {char[][] mazeChars = {{'1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},{'1', '0', '0', '1', '1', '1', '0', '0', '1', '1'},{'1', '0', '0', '1', '1', '0', '0', '1', '0', '1'},{'1', '0', '0', '0', '0', '0', '0', '1', '0', '1'},{'1', '0', '0', '0', '0', '1', '1', '0', '0', '1'},{'1', '0', '0', '1', '1', '1', '1', '0', '0', '1'},{'1', '0', '0', '0', '0', '1', '0', '1', '0', '1'},{'1', '0', '1', '1', '0', '0', '0', '1', '0', '1'},{'1', '1', '0', '0', '0', '0', '0', '0', '0', '1'},{'1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},};Maze maze = new Maze(mazeChars);System.out.println("The maze is shown:");maze.printMaze();Scanner scanner = new Scanner(System.in);int sx, sy, ex, ey;System.out.print("Enter the line where the starting point is located(1-8): ");sx = scanner.nextInt();System.out.print("Enter the column where the starting point is located(1-8): ");sy = scanner.nextInt();System.out.print("Enter the line where the ending point is located(1-8): ");ex = scanner.nextInt();System.out.print("Enter the column where the ending point is located(1-8): ");ey = scanner.nextInt();maze.findPath(sx, sy, ex, ey);}private Cell[][] cells;public Maze(char[][] maze) {this.cells = createMaze(maze); //创建迷宫}private Cell[][] createMaze(char[][] maze) {Cell[][] cells = new Cell[maze.length][];for (int i = 0; i < maze.length; i++) {cells[i] = new Cell[maze[i].length];for (int j = 0; j < cells[i].length; j++) {cells[i][j] = new Cell(i, j, maze[i][j], false);}}return cells;}public void printMaze() {for (int i = 0; i < cells.length; i++) {for (int j = 0; j < cells[i].length; j++) {System.out.print(cells[i][j].c + " ");}System.out.println();}}public void findPath(int sx, int sy, int ex, int ey) {if (cells[sx][sy].c == '1' || cells[ex][ey].c == '1') {throw new RuntimeException("You entered the wrong start or end position.");}int countOfNewline = 0; //输出换行标志（输出5个坐标后换行）LinkedListStack<Cell> stack = new LinkedListStack<>();Cell startCell = cells[sx][sy];Cell endCell = cells[ex][ey];stack.push(startCell);startCell.visited = true;while (!stack.isEmpty()) {Cell current = stack.getTop();if (current == endCell) {while (!stack.isEmpty()) {Cell cell = stack.pop();cell.c = '*';countOfNewline++;while (!stack.isEmpty() && !isAdjoinCell(cell, stack.getTop())) {//除去寻找路径过程中可以通过但未在路径上的坐标stack.pop();}if (!stack.isEmpty()) {if (stack.getTop().x == cell.x) {cell.d = stack.getTop().y - cell.y == 1 ? 1 : 3;}if (stack.getTop().y == cell.y) {cell.d = stack.getTop().x - cell.x == 1 ? 2 : 4;}}System.out.printf("(%d, %d, %d)\t", cell.x, cell.y, cell.d);if (countOfNewline % 5 == 0) {System.out.println();}}System.out.println("\nFind the path from start to end:");printMaze();return;} else {int x = current.x;int y = current.y;int count = 0;if (isValidWayCell(cells[x][y + 1])) { //向东（向右）stack.push(cells[x][y + 1]);cells[x][y + 1].visited = true;count++;}if (isValidWayCell(cells[x + 1][y])) { //向南（向下）stack.push(cells[x + 1][y]);cells[x + 1][y].visited = true;count++;}if (isValidWayCell(cells[x][y - 1])) { //向西（向左）stack.push(cells[x][y - 1]);cells[x][y - 1].visited = true;count++;}if (isValidWayCell(cells[x - 1][y])) { //向北（向上）stack.push(cells[x - 1][y]);cells[x - 1][y].visited = true;count++;}if (count == 0) { //如果是死点，出栈stack.pop();}}}System.out.println("There is no path from start to end.");}private boolean isAdjoinCell(Cell cell, Cell topCell) {if (cell.x == topCell.x && Math.abs(cell.y - topCell.y) < 2) {return true;}if (cell.y == topCell.y && Math.abs(cell.x - topCell.x) < 2) {return true;}return false;}private boolean isValidWayCell(Cell cell) {return cell.c == '0' && !cell.visited;}}class Cell {int x; //单元所在行int y; //单元所在列int d; //找到终点后路径上单元个对其下一个单元格的指向 1、2、3、4 分别表示东南西北（右、下、左、上）boolean visited = false; //是否曾经进栈char c; //1代表该位置是墙，0代表是通路，*代表该位置在路径上public Cell(int x, int y, char c, boolean visited) {this.x = x;this.y = y;this.c = c;this.visited = visited;}
}所用链栈代码
public class LinkedListStack<T> {private LinkedListStackNode<T> head;private int size;public LinkedListStack() {size = 0;}public LinkedListStackNode<T> getHead() {return head;}public int getSize() {return size;}public boolean isEmpty() {return size == 0;}public void push(T element) {LinkedListStackNode<T> node = new LinkedListStackNode<>(element);node.setNext(head);head = node;size++;}public T pop() {if (!isEmpty()) {T element = head.getData();head = head.getNext();size--;return element;} else {throw new RuntimeException("The stack is empty.");}}public T getTop() {if (!isEmpty()) {return head.getData();} else {throw new RuntimeException("The stack is empty.");}}public void display() {if (isEmpty()) {throw new RuntimeException("The stack is empty.");}LinkedListStackNode<T> linkedListStackIndexNode = head;while (linkedListStackIndexNode != null) {System.out.print(linkedListStackIndexNode.getData() + "\t");linkedListStackIndexNode = linkedListStackIndexNode.getNext();}System.out.println();}
}class LinkedListStackNode<T> {private T data;private LinkedListStackNode<T> next;public LinkedListStackNode() { }public LinkedListStackNode(T data) {this.data = data;}public T getData() {return data;}public void setData(T data) {this.data = data;}public LinkedListStackNode<T> getNext() {return next;}public void setNext(LinkedListStackNode<T> next) {this.next = next;}
}