Java迷宫算法问题（用栈实现）有算法简述

Java迷宫算法问题（用栈实现）有算法简述

import java.io.File;
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("
");
}
LinkedList> trace = new LinkedList>();
System.out.println(maze(Mazemap, trace));
System.out.println(trace);
}

public static boolean maze(char[][] maze,
List> trace) {
LinkedList> path = new LinkedList>();
HashSet> traverse = new HashSet>();

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(i, j));
}
}
}
while (!path.isEmpty()) {
TwoTuple 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(temp.first,
temp.second + 1));
if (temp.second - 1 > 0
&& maze[temp.first][temp.second - 1] != 'W')
path.add(new TwoTuple(temp.first,
temp.second - 1));
if (temp.first + 1 < maze.length
&& maze[temp.first + 1][temp.second] != 'W')
path.add(new TwoTuple(temp.first + 1,
temp.second));
if (temp.first - 1 > 0
&& maze[temp.first - 1][temp.second] != 'W')
path.add(new TwoTuple(temp.first - 1,
temp.second));
traverse.add(temp);
trace.add(temp);
}
}
trace.clear();
return false;
}
}

class TwoTuple {
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 stack=new LinkedList();
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