Как сгенерировать двоичное дерево из лабиринта? - PullRequest
Новая
       29

Как сгенерировать двоичное дерево из лабиринта?

0 голосов
/ 10 ноября 2011

Матрица размером 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 - выход излабиринт.Цель этой программы - создать двоичное дерево, которое будет описывать все пути, по которым мы шли, пытаясь найти выход.

Как бы вы это сделали?Я действительно потерян в этот раз, я не знаю, с чего начать, поэтому я не публикую ничего из того, что попробовал, но, если вы могли бы дать мне направление, я был бы очень благодарен.

Джон Смит.

1 Ответ

1 голос
/ 21 ноября 2011

вы можете попробовать возврат

вот полный пример того, как решить эту проблему ... однако: он не может работать в лабиринте с "островками" в немкак было бы необходимо дополнительно отслеживать, где вы уже были.но я думаю, что вы можете понять, как это сделать ...

вывод должен быть:
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));

    }
}
...