本文共 4385 字，大约阅读时间需要 14 分钟。

【问题描述】

以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

【算法分析】

主要考查数据结构-栈。栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

详细请看百度百科： 

【实现分析】

可使用回溯方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。

【代码展示】

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
   
     stack;	boolean p[][] = null;	public Maze() {		maze = new int[15][15];		stack = new Stack
    
     ();		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 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
     
       newPos = new Stack
      
       ();		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 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	#	#

转载地址：http://gskai.baihongyu.com/