Question

急需一java高手帮忙写一迷宫程序

写一走迷宫的程序:
6 6
5 5 5 5 5 5
0 0 0 0 0 5
5 5 0 5 0 5
5 5 0 5 5 5
5 0 0 0 0 0
5 5 5 5 5 5
1 0
需要一个可以读取以上txt文档的程序:
第一行,读取6 6, 建立一个6X6的2D array
中间那段是array的数据,也就是迷宫
最后一行是迷宫的起点
然后要找出口,0是可以走的,5是不能走的,
程序需要print 那个迷宫,以及最后正确的路
例如上面那个迷宫的正确路线是:
<1,0>, <1,1>, ........, <4,5> (0所在的index)
请把程序发到email 574435755@qq.com
测过正确就会给分
需要使用以下:
import stackpackage.*;
也就是import以下两程序
package stackpackage;
import java.util.LinkedList;
public class Stack {
private LinkedList stack;

public Stack() {
stack = new LinkedList();
}

public boolean isEmpty() {
return stack.size() == 0;
}

public Object pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
return stack.removeFirst();
}

public void push(Object obj) {
stack.addFirst(obj);
}

public Object peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return stack.peek();
}
}

package stackpackage;
public class EmptyStackException extends RuntimeException {
public EmptyStackException(String msg) {
super(msg);
}

public EmptyStackException() {
super();
}
}
注意开始在第一行的时候,程序容易直接当开始是出口

Answer 1

给你代码，你给出的那两个类，不能满足，我的需要，我就没有使用。
你看一下吧。
----------------------------------------
package stackpackage;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Maze {
// 上
private static Point directionTop = new Point(-1, 0);
// 下
private static Point directionBottom = new Point(1, 0);
// 左
private static Point directionLeft = new Point(0, -1);
// 右
private static Point directionRight = new Point(0, 1);
private static Point[] directions = { directionTop, directionRight,
directionBottom, directionLeft };
private static boolean isStop = false;
private static int row = 0;
private static int col = 0;
private static Point startPoint = new Point();
public static void main(String[] args) throws Exception {
FileReader fr = new FileReader("data.txt");
BufferedReader br = new BufferedReader(fr);
int rowIndex = 1;
int[][] maze = null;
while (br.ready()) {
String line = br.readLine();
Scanner sc = new Scanner(line);
if (rowIndex == 1) {
row = sc.nextInt();
col = sc.nextInt();
maze = new int[row][col];
} else {
if (rowIndex < row + 2) {
for (int i = 0; i < col; i++) {
maze[rowIndex - 2][i] = sc.nextInt();
}
} else {
startPoint.x = sc.nextInt();
startPoint.y = sc.nextInt();
}
}
rowIndex++;
}
List<Point> route = new ArrayList<Point>();
route.add(startPoint);
findNext(startPoint);
puzzle(maze, startPoint, route);
System.out.println(route);
}
private static void puzzle(int[][] maze, Point p, List<Point> route) {
if (isStop) {
return;
}
Point[] nextDirections = p.nextDirections;
for (int i = 0; i < nextDirections.length; i++) {
if (isStop) {
return;
}
Point direction = nextDirections[i];
Point newP = new Point(p.x + direction.x, p.y + direction.y);
if (newP.isEffective() && maze[newP.x][newP.y] == 0
&& !route.contains(newP)) {
newP.before = p;
findNext(newP);
route.add(newP);
if (isExit(newP)) {
isStop = true;
break;
}
puzzle(maze, newP, route);
}
}
if (isStop) {
return;
}
route.remove(route.size() - 1);
}
private static void findNext(Point p) {
int index = 0;
Point[] nextDirections = new Point[3];
for (int i = 0; i < nextDirections.length; i++) {
nextDirections[i] = new Point(0, 0);
}
for (int i = 0; i < directions.length; i++) {
Point direction = directions[i];
Point newP = new Point(p.x + direction.x, p.y + direction.y);
if (newP.isEffective() && !newP.equals(p.before) && newP.x < row
&& newP.y < col) {
nextDirections[index++] = direction;
}
}
p.nextDirections = nextDirections;
}
private static boolean isExit(Point p) {
if (startPoint.equals(p)) {
return false;
}
for (int i = 0; i < directions.length; i++) {
Point direction = directions[i];
Point newP = new Point(p.x + direction.x, p.y + direction.y);
if (!newP.equals(p.before)
&& (newP.x >= row || newP.y >= col || newP.x < 0 || newP.y < 0)) {
return true;
}
}
return false;
}
}
class Point {
int x = 0;
int y = 0;
Point[] nextDirections = null;
Point before = null;
public Point() {
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public String toString() {
return "<" + x + "," + y + ">";
}
public boolean isEffective() {
return x >= 0 && y >= 0;
}
public boolean equals(Object obj) {
return equals((Point) obj);
}
public boolean equals(Point p) {
if (p == null) {
return false;
}
return this.x == p.x && this.y == p.y;
}
}

Answer 2

如果你现在的程序会把入口直接当出口，那么你就把出口给先封住了就是。。

追问

迷宫是给的,怎么封?

追答

你可以给已经给出的矩阵，添加一个边框，例如，你把3*3的矩阵，镶嵌在5*5的矩阵中间。边框的外围数值全部设为 障碍（出口除外） 这样不就可以了吗？

Answer 3

这要用到AA算法，自己百度一下javaAA算法吧

Answer 4

存在多个真确路线的情况么？

追问

按顺时针找路线,所以第一个按顺时针找的路线就是答案,不过给的迷宫应该是只有一个正确路线的