import java.io.FileNotFoundException
import java.util.HashSet
import java.util.LinkedList
import java.util.List
import java.util.Scanner
public class Test {
public static void main(String[] args) throws FileNotFoundException {
Scanner input = new Scanner(new File("Maze2tong.txt"))
int row = 0
char[][] Mazemap = new char[12][58]
while (input.hasNext()) {
String line = input.nextLine()
for (int column = 0 column <= line.length() - 1 column++) {
char c = line.charAt(column)
Mazemap[row][column] = c
}
row++
}
for (int i = 0 i < 12 i++) {
for (int j = 0 j < 58 j++) {
System.out.print(Mazemap[i][j])
}
System.out.print("\n")
}
LinkedList<TwoTuple<Integer, Integer>> trace = new LinkedList<TwoTuple<Integer, Integer>>()
System.out.println(maze(Mazemap, trace))
System.out.println(trace)
}
public static boolean maze(char[][] maze,
List<TwoTuple<Integer, Integer>> trace) {
LinkedList<TwoTuple<Integer, Integer>> path = new LinkedList<TwoTuple<Integer, Integer>>()
HashSet<TwoTuple<Integer, Integer>> traverse = new HashSet<TwoTuple<Integer, Integer>>()
for (int i = 0 i < maze.length i++) {
for (int j = 0 j < maze[i].length j++) {
if (maze[i][j] == 'S') {
path.add(new TwoTuple<Integer, Integer>(i, j))
}
}
}
while (!path.isEmpty()) {
TwoTuple<Integer, Integer> temp = path.pop()
if (traverse.contains(temp)) {
continue
} else if (maze[temp.first][temp.second] == 'F') {
trace.add(temp)
return true
} else if (!traverse.contains(temp)) {
if (temp.second + 1 < maze[temp.first].length
&& maze[temp.first][temp.second + 1] != 'W')
path.add(new TwoTuple<Integer, Integer>(temp.first,
temp.second + 1))
if (temp.second - 1 > 0
&& maze[temp.first][temp.second - 1] != 'W')
path.add(new TwoTuple<Integer, Integer>(temp.first,
temp.second - 1))
if (temp.first + 1 < maze.length
&& maze[temp.first + 1][temp.second] != 'W')
path.add(new TwoTuple<Integer, Integer>(temp.first + 1,
temp.second))
if (temp.first - 1 > 0
&& maze[temp.first - 1][temp.second] != 'W')
path.add(new TwoTuple<Integer, Integer>(temp.first - 1,
temp.second))
traverse.add(temp)
trace.add(temp)
}
}
trace.clear()
return false
}
}
class TwoTuple<A, B> {
public final A first
public final B second
public TwoTuple(A a, B b) {
first = a
second = b
}
@Override
public int hashCode() {
return first.hashCode() + second.hashCode()
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof TwoTuple)) {
}
return obj instanceof TwoTuple && first.equals(((TwoTuple) obj).first)
&& second.equals(((TwoTuple) obj).second)
}
public String toString() {
return "(" + first + ", " + second + ")"
}
} // /:-
import java.io.File
import java.io.FileNotFoundException
import java.util.LinkedList
import java.util.Scanner
class MyPoint
{
public boolean visited=false
public int parentRow=-1
public int parentColumn=-1
public final char content
public int x
public int y
public MyPoint(char c,int x,int y)
{
this.content = c
this.x = x
this.y = y
}
}
public class Maze
{
public static MyPoint[][] getMazeArray(){
Scanner input = null
MyPoint[][] mazemap = new MyPoint[12][58]
try {
input = new Scanner(new File("Maze2tong.txt"))
int row = 0
while (input.hasNext()) {
String line = input.nextLine()
for (int column = 0 column <= line.length() - 1 column++) {
char c = line.charAt(column)
MyPoint point = new MyPoint(c,row,column)
mazemap[row][column] = point
}
row++
}
input.close()
} catch (FileNotFoundException e) {
e.printStackTrace()
}
return mazemap
}
public static boolean tomRun(MyPoint[][] maze,MyPoint end)
{
int x = maze.length
int y = maze[0].length
LinkedList<MyPoint> stack=new LinkedList<MyPoint>()
for (int i = 0 i < maze.length i++) {
for (int j = 0 j < maze[i].length j++) {
if (maze[i][j].content == 'S') {
stack.push(maze[i][j])
maze[i][j].visited=true
}
}
}
boolean result=false
while(!stack.isEmpty())
{
MyPoint t=stack.pop()
//System.out.println("pop point:"+t.x+" "+t.y+" value:"+maze[t.x][t.y])
if(t.content == 'F')
{
result=true
end.x = t.x
end.y = t.y
break
}
if(t.x-1 > 0 && maze[t.x-1][t.y].visited==false && maze[t.x-1][t.y].content != 'W')
{
stack.push(maze[t.x-1][t.y])
maze[t.x-1][t.y].parentRow=t.x
maze[t.x-1][t.y].parentColumn=t.y
maze[t.x-1][t.y].visited=true
}
if(t.x + 1 < x && maze[t.x+1][t.y].visited==false && maze[t.x+1][t.y].content != 'W')
{
stack.push(maze[t.x+1][t.y])
maze[t.x+1][t.y].parentRow=t.x
maze[t.x+1][t.y].parentColumn=t.y
maze[t.x+1][t.y].visited=true
}
if(t.y - 1 > 0 && maze[t.x][t.y - 1].visited==false && maze[t.x][t.y-1].content != 'W')
{
stack.push(maze[t.x][t.y-1])
maze[t.x][t.y-1].parentRow=t.x
maze[t.x][t.y-1].parentColumn=t.y
maze[t.x][t.y-1].visited=true
}
if( t.y + 1 < y && maze[t.x][t.y + 1].visited==false && maze[t.x][t.y+1].content != 'W')
{
stack.push(maze[t.x][t.y+1])
maze[t.x][t.y+1].parentRow=t.x
maze[t.x][t.y+1].parentColumn=t.y
maze[t.x][t.y+1].visited=true
}
}
return result
}
public static void show(int x,int y,MyPoint[][] visited)
{
if(visited[x][y].parentRow==-1)
{
System.out.println("["+x+","+y+"]")
return
}
show(visited[x][y].parentRow,visited[x][y].parentColumn,visited)
System.out.println("->"+"["+x+","+y+"]")
}
public static void main(String[] args)
{
MyPoint[][] maze = getMazeArray()
MyPoint point = new MyPoint('c',1,1)
if(tomRun(maze,point))
{
System.out.println("逃生路径如下：")
show(point.x,point.y,maze)
}
else
System.out.println("无法走出迷宫！")
}
} WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WSOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOWOOOOOOW
WWOOOOOOOOOOOOOWWWWWWWWWWWWWOOOOOOOOOOWWWWWWWWWWWWWOOOOOOW
WWWWWWOOOOOOOOOOOOWWWWWWWOOOOOOOOOOOOWWWWWWWWWWWWWWWWOOOOW
WOOOOOOWWWWWWWWWWWWWWOOOOOOOOOOOWWWWWWWWWWWWWWWWWWWWWWWWWW
WOOOOWWWWWWWOOOOOOWWWWOOOOOOWWWWWWWWWWWOOOOWWWWWWWWWOWWWWW
WOOOWWWWWWWWWWWWOOWWWWWWWWWWWWOOOOOOOOOOOOWWWWWWWWWOOOOOWW
WOOWWWWWWWWWWWWWOOWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWWOOOW
WOWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWOOW
WOWWWWWWWWWWWWWOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWWWWWWWWOOW
WOOOOOOOOOOOOOOOOWWWWOOOOOOOOWWWWWWWOOOOOOWWWWWWWWWWWWWWFW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WSOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOWOOOOOOW
WWOOOOOOOOOOOOOWWWWWWWWWWWWWOOOOOOOOOOWWWWWWWWWWWWWOOOOOOW
WWWWWWOOOOOOOOOOOOWWWWWWWOOOOOOOOOOOOWWWWWWWWWWWWWWWWOOOOW
WOOOOOOWWWWWWWWWWWWWWOOOOOOOOOOOWWWWWWWWWWWWWWWWWWWWWWWWWW
WOOOOWWWWWWWOOOOOOWWWWOOOOOOWWWWWWWWWWWOOOOOOOOOOOOOOOOOWW
WOOOWWWWWWWWWWWWOOWWWWWWWWWWWWOOOOOOOOOOOOWWWWWWWWWOOOOOWW
WOOWWWWWWWWWWWWWOOWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWWOOOW
WOWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWOOW
WOWWWWWWWWWWWWWOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWWWWWWWWOOW
WOOOOOOOOOOOOOOOOWWWWOOOOOOOOWWWWWWWOOOOOOWWWWWWWWWWWWWWFW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
首先给定一个初始坐标，然后构建一个容器保存坐标值，之后进行迭代，横坐标+1，或者纵坐标+1，这个顺寻自己定义（四个方向），经过的“路径”保存在那个容器中，如果遇到死角，以此往回迭代，在容器中将遇到死角的那个坐标删除。最后找到自己定义的那个迷宫出口坐标。
