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

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、背景：《数据结构》在软件工程中是一门综合性的专业基础课。数据结构的研究性不仅涉及到计算机硬件（特别是编码理论、储存装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编程还是 *** 作系统，都涉及到数据元素在存储器中的分配问题。

2、课程设计的目的和意义：目的是综合运用所学的数据结构知识完成对走迷宫的编程，达到加深对数据结构了解的目的，扩展数据结构方面的知识。意义是通过本次课程设计，可以培养独立思考、综合运用所学有关相应知识的能力，能更好的巩固java数据结构课程学习的内容，学会理论与实践相结合。掌握基本的分析问题和利用计算机求解问题，具备初步的高级语言程序设计能力，为以后的课程和毕业设计做好准备。