0

一个 150x150 大小的矩阵将描述我们的迷宫,例如,如果矩阵只有 10x10,我们将有如下内容:

   1 1 1 1 1 1 1 1 1 1
   1 0 0 0 0 0 0 1 0 0<-F
   1 0 1 1 0 1 0 1 0 1 
   1 1 1 1 0 1 0 0 0 1
   1 1 1 1 0 1 1 1 1 1
   1 0 0 0 0 1 1 1 1 1
   1 0 1 1 0 1 1 1 1 1
   1 0 1 0 0 0 0 1 1 1
S->0 0 1 1 1 1 0 1 1 1
   1 1 1 1 1 1 1 1 1 1

其中 S 表示起点,F 表示迷宫的出口。这个程序的目的是生成一个二叉树,它将描述我们在试图找到出口时走过的所有路径。

你将如何做到这一点?这次我真的迷路了,我真的不知道从哪里开始,这就是为什么我没有发布任何我尝试过的东西,但如果你能给我一个方向,我将非常感激。

约翰·史密斯。

4

1 回答 1

1

你可能想尝试回溯

这是如何解决此问题的完整示例...但是:它不能在其中包含“岛屿”的迷宫上运行,因为有必要额外跟踪您已经去过的地方。但我认为你也可以弄清楚如何做到这一点......

输出应该是:
right, up, up, up, right, right, right, up, up, up, up, right, right, down, down, right, right, up, up, right, finish!

import java.awt.Point;

public class Maze {

    enum Direction {
        up, right, down, left
    }

    static Direction[] dirs = Direction.values();

    int[][] maze = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
            { 1, 0, 0, 0, 0, 0, 0, 1, 0, 0 }, { 1, 0, 1, 1, 0, 1, 0, 1, 0, 1 },
            { 1, 1, 1, 1, 0, 1, 0, 0, 0, 1 }, { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
            { 1, 0, 0, 0, 0, 1, 1, 1, 1, 1 }, { 1, 0, 1, 1, 0, 1, 1, 1, 1, 1 },
            { 1, 0, 1, 0, 0, 0, 0, 1, 1, 1 }, { 0, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
    Point start = new Point(0, 8);
    Point finish = new Point(9, 1);

    Point go(Direction dir, Point from) {
        Point result = new Point(from);
        switch (dir) {
        case up:
            if ((from.y == 0) || (maze[from.y - 1][from.x] != 0))
                return null;
            result.translate(0, -1);
            break;
        case right:
            if ((from.x == maze[0].length) || (maze[from.y][from.x + 1] != 0))
                return null;
            result.translate(1, 0);
            break;
        case down:
            if ((from.y == maze.length) || (maze[from.y + 1][from.x] != 0))
                return null;
            result.translate(0, 1);
            break;
        case left:
            if ((from.x == 0) || (maze[from.y][from.x - 1] != 0))
                return null;
            result.translate(-1, 0);
            break;
        }
        return result;
    }

    String tryToGo(Direction dir, Point from) {
        String result;
        Point newPosition = go(dir, from);
        if (newPosition == null)
            return null;
        else if (newPosition.equals(start))
            return null;
        else if (newPosition.equals(finish))
            return "finish!";
        else {
            for (Direction newDir : dirs) {
                switch (newDir) {
                case up:
                    if (dir == Direction.down)
                        continue;
                    break;
                case down:
                    if (dir == Direction.up)
                        continue;
                    break;
                case left:
                    if (dir == Direction.right)
                        continue;
                    break;
                case right:
                    if (dir == Direction.left)
                        continue;
                    break;
                }
                result = tryToGo(newDir, newPosition);
                if (result == null)
                    continue;
                else
                    return newDir + ", " + result;
            }
            return null;
        }
    }

    public static void main(String[] args) {
        Maze maze = new Maze();
        System.out.println("right" + maze.tryToGo(Direction.right, maze.start));

    }
}
于 2011-11-21T10:04:12.047 回答