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

这是给的算法createanemptystackoflocationstoexplore.pushthestartlocationontothestack.while(s... 这是给的算法
create an empty stack of locations to explore.
push the start location onto the stack.
while ( stack is not empty ) {
pop a location loc from the stack.
if we have pulled loc from the stack before:
no need to explore it again, so skip loc.
if loc is the end location:
the end was reachable!
else, loc is a new reachable non-finish location, so explore it:
add all non-wall adjacent maze locations to the stack.
record the fact that we have explored loc.
}
if the stack is empty, the finish is unreachable
1.
只用用栈或者队列（stack or queue）
并且只能在一个class里完成，不能call任何的point class
要求是写一个函数返回值为true 或者false
true代表迷宫可以走通，
false代表不可以。
不用考虑最短路径，只要可以走通就可以。
迷宫如下 F代表终点，W是墙，O是可以走得路 S是起始点。
2.

解决以上问题然后保存可以通过的路，并且输出。展开

 我来答

1个回答

#热议# 什么是淋病？哪些行为会感染淋病？

每天学点Java
2014-02-27 · TA获得超过5938个赞

知道大有可为答主

回答量：3547

采纳率：0%

帮助的人：1332万

我也去答题访问个人页

关注

展开全部

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("\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

已赞过 已踩过<

评论收起

推荐律师服务：若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询

您可能关注的内容

商汤科技日日新·CoRaccoon-AI代码辅助生成

基于商汤大模型，让AI帮你写代码，支持100+语言与主流IDE，提升编程效率超50%。涵盖多场景，已助数万用户提升效率。点击立即体验!

2024版Java面试题-Java面试题&笔试超5000道~超级码客

涵盖java 面试算法海量Java面试题题#Java语言，多线程，JVM，SpringBoot，SpringCloud，Dubbo，Java微服务，Java数据结构算法，MyBatis，Hibernate等Java面试题超5000题java 面试算法

www.chaojimake.cn广告

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

您可能关注的内容

其他类似问题

为你推荐：