必ず解ける迷路 in Java DouKaku?

必ず解ける迷路

以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。

1. 格子状の迷路であること。
2. 経路の幅は均等であること。
3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。
   ループも認めません。
4. 出力の度にランダムな迷路であること。
   ランダムシードが同じ時に同じ迷路になってしまうのはよいです。

たとえば、n=4, m=5の迷路の出力は以下のようになります。

　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■　　　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　■　　　■　■
―■■■■■■■■■

こう言うのは、×の部分が3のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■×■　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■■■　■
４■　■×××■　■
―■　■×■■■　■
５■　■×××■　■
―■■■■■■■■■

このようなループも2のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　　　■　■
―■■■　■　■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　　　　　■　■
―■■■■■■■■■

できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。


難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を
どうやって作るのかを考えると答えが見えてくると思います。
ソースコードはJavaで150行程度になりました。

post comment

Posted feedbacks - Java

メモリを O(n) でしか使わないのを書いてみました。
最後の行で辻褄を合わせていますが、それなりな迷路になっているかと思います。

n=4, m=5, seed=6 でこんな感じになりました。

■■■■■■■■■
■　■　　　■　■
■　■　■■■　■
■　■　　　　　■
■　■　■■■■■
■　　　■　■　■
■■■　■　■　■
■　　　　　■　■
■■■■■　■　■
■　　　　　　　■
■■■■■■■■■

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Iterator;
import java.util.Random;


public class Sample123 {
    public static void main(String[] args) {
        try {
            BufferedWriter writer = new BufferedWriter(new FileWriter("result.txt"));

            long start = System.currentTimeMillis();
            Iterator<String> ite = new MazeLineIterator(4, 5, 6);
            while (ite.hasNext()) {
                writer.append(ite.next());
                writer.newLine();
            }
            long end = System.currentTimeMillis();

            writer.close();
            System.out.println("elapse: " + (end - start) + "(ms)");
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }
}

class MazeLineIterator implements Iterator<String> {
    public static final String WALL_CHAR = "■";
    public static final String SPACE_CHAR = "　";

    private static final int WALL_AREA = 0;

    private final Random random_;

    private long line_ = -1;
    private boolean oddLine_ = false;    // oddLine_ == true の時が通路の行、falseの時が柱の行
    private int counter_ = 1;

    private final int maxCol_;
    private final long maxRow_;
    private final int[] mazeLine_;

    public MazeLineIterator(int col, long row) {
        maxCol_ = col;
        maxRow_ = row;
        mazeLine_ = new int[col * 2 + 1];
        random_ = new Random();
    }
    public MazeLineIterator(int col, long row, long seed) {
        maxCol_ = col;
        maxRow_ = row;
        mazeLine_ = new int[col * 2 + 1];
        random_ = new Random(seed);
    }


    public boolean hasNext() {
        return (line_ < maxRow_);
    }

    public String next() {
        if (line_ < 0 || (line_ == maxRow_ - 1 && !oddLine_)) {
            for (int index = 0; index < mazeLine_.length; index++) {
                mazeLine_[index] = WALL_AREA;
            }
        } else {
            if (oddLine_) {
                createOddLine();
            } else {
                createEvenLine();
            }
        }

        if (!oddLine_) line_++;
        oddLine_ = !oddLine_;
        return createDisplay(mazeLine_);
    }

    private String createDisplay(int[] line) {
        StringBuilder builder = new StringBuilder(line.length);
        for (int index: line) {
            //builder.append(index);
            builder.append(isWall(index)? WALL_CHAR: SPACE_CHAR);
        }
        return builder.toString();
    }


    private void createOddLine() {
        int area = 0;
        for (int index = 0; index < maxCol_; index++) {
            int lastArea = mazeLine_[index * 2 + 1];
            if (isWall(lastArea)) {
                if (isWall(area)) {
                    area = counter_++;
                }
                mazeLine_[index * 2 + 1] = area;
            } else {
                if (!isWall(area)) {
                    if (area == lastArea) {
                        mazeLine_[index * 2] = WALL_AREA;
                    } else {
                        area = replaceArea(area, lastArea);
                    }
                } else {
                    area = lastArea;
                }
            }

            if (index > 0 && line_ == maxRow_ - 1) {
                if (mazeLine_[index * 2 + 1] != mazeLine_[index * 2 - 1]) {
                    area = replaceArea(mazeLine_[index * 2 - 1], mazeLine_[index * 2 + 1]);
                    mazeLine_[index * 2] = area;
                }
            }
            if (index == maxCol_ - 1) break;
            if (random_.nextBoolean()) {
                area = WALL_AREA;
            }
            mazeLine_[(index + 1) * 2] = area;
        }
    }

    private void createEvenLine() {
        for (int index = 0; index < maxCol_; index++) {
            int lastArea = mazeLine_[index * 2 + 1];
            if (searchArea(lastArea, index * 2 + 1) && random_.nextBoolean()) {
                mazeLine_[index * 2 + 1] = WALL_AREA;
            }
            mazeLine_[(index + 1) * 2] = WALL_AREA;
        }
    }

    private boolean isWall(int area) {
        return (area == WALL_AREA);
    }
    private int replaceArea(int oldArea, int newArea) {
        if (oldArea < newArea) {
            return replaceArea(newArea, oldArea);
        }
        for (int index = 0; index < mazeLine_.length; index++) {
            if (mazeLine_[index] == oldArea) {
                mazeLine_[index] = newArea;
            }
        }
        if (oldArea == counter_) {
            counter_--;
        }
        return newArea;
    }

    private boolean searchArea(int area, int excludeIndex) {
        for (int index = 0; index < mazeLine_.length; index++) {
            if (index == excludeIndex) continue;
            if (mazeLine_[index] == area) return true;
        }
        return false;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}

初投稿です。
格子点をdisjoint setとして管理し、でたらめな順序で壁を立てていく方法です。

実行時間は、5回の実行で以下のとおりでした。
6.063, 6.546, 5.968, 6.188, 6.172 (秒)
[CoreSolo U1300 (1.06GHz), 512MB memory] (Panasonic Let's note CF-R5)

import java.util.ArrayList;
import java.util.List;

public class Maze {

    private static class Pole {
        Pole parent;
        Pole() { this.parent = this; }
        Pole getRoot() {
            return (parent == this ? this : (parent = parent.getRoot()));
        }
    }

    private static class Point {
        int x;
        int y;
        Point(int x, int y) { this.x = x; this.y = y; }
    }

    private int w;
    private int h;
    private boolean[][] hWalls;
    private boolean[][] vWalls;
    private Pole[][] poles;
    private Pole pTL;
    private Pole pBR;
    private List<Point> buildSequence;

    public Maze(int w, int h) {
        this.w = w;
        this.h = h;
    }

    public void build() {
        initialize();
        for (Point p : buildSequence) {
            buildWall(p);
        }
    }

    public void initialize() {
        initializeWalls();
        initializePolls();
        initializeBuildSequence();
    }

    private void initializeWalls() {
        hWalls = new boolean[w / 2][h / 2 - 1];
        vWalls = new boolean[w / 2 - 1][h / 2];
    }

    private void initializePolls() {
        poles  = new Pole[w / 2 + 1][h / 2 + 1];
        int pw = poles.length;
        int ph = poles[0].length;
        for (int x = 0; x < pw; x++) {
            for (int y = 0; y < ph; y++) {
                poles[x][y] = new Pole();
            }
        }
        pTL = poles[0][0];
        pBR = poles[pw - 1][ph - 1];
        for (int x = 1; x < pw; x++) {
            poles[x][0].parent = pTL;
            poles[pw - 1 - x][ph - 1].parent = pBR;
        }
        for (int y = 1; y < ph - 1; y++) {
            poles[pw - 1][y].parent = pTL;
            poles[0][ph - 1 - y].parent = pBR;
        }
    }

    private void initializeBuildSequence() {
        buildSequence = new ArrayList<Point>();
        for (int x = 1; x < w - 1; x += 2) {
            for (int y = 2; y < h - 2; y += 2) {
                buildSequence.add(new Point(x, y));
            }
        }
        for (int x = 2; x < w - 2; x += 2) {
            for (int y = 1; y < h - 1; y += 2) {
                buildSequence.add(new Point(x, y));
            }
        }
        for (int i = 0; i < buildSequence.size(); i++) {
            int j = (int) (Math.random() * buildSequence.size());
            Point pTmp = buildSequence.get(i);
            buildSequence.set(i, buildSequence.get(j));
            buildSequence.set(j, pTmp);
        }
    }

    public void buildWall(Point p) {
        Pole p1 = poles[p.x / 2][p.y / 2];
        Pole p2 = poles[(p.x + 1) / 2][(p.y + 1) / 2];
        if (isConnectable(p1, p2)) {
            if (p.x % 2 == 0) {
                vWalls[p.x / 2 - 1][p.y / 2] = true;
            } else {
                hWalls[p.x / 2][p.y / 2 - 1] = true;
            }
        }
    }

    private boolean isConnectable(Pole p1, Pole p2) {
        Pole r1 = p1.getRoot();
        Pole r2 = p2.getRoot();
        if (r1 == r2) {
            return false;
        } else {
            Pole rTL = pTL.getRoot();
            Pole rBR = pBR.getRoot();
            if (r1 == rTL && r2 == rBR || r1 == rBR && r2 == rTL) {
                return false;
            } else {
                r2.parent = r1;
                return true;
            }
        }
    }

    public boolean isWall(int x, int y) {
        if (x == 0 || x == w - 1 || y == 0 || y == h - 1) {
            return true;
        } else if (x % 2 == 0 && y % 2 == 1) {
            return vWalls[x / 2 - 1][y / 2];
        } else if (x % 2 == 1 && y % 2 == 0) {
            return hWalls[x / 2][y / 2 - 1];
        } else {
            return x % 2 == 0;
        }
    }

    public static void main(String args[]) {
        int w = Integer.parseInt(args[0]) * 2 + 1;
        int h = Integer.parseInt(args[1]) * 2 + 1;
        long begin = System.currentTimeMillis();
        Maze maze =    new Maze(w, h);
        maze.build();
        long end = System.currentTimeMillis();
        System.out.println("Elapsed time: " + (end - begin) / 1000.0 + " sec.");
        // print(maze);
    }

    private static void print(Maze maze) {
        for (int y = 0; y < maze.h; y++) {
            for (int x = 0; x < maze.w; x++) {
                System.out.print(maze.isWall(x, y) ? '■' : '　');
            }
            System.out.println();
        }
    }
}

DouKaku?

必ず解ける迷路

Posted feedbacks - Java

Index

Feed

Other

Link

Pathtraq