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 に答える