必ず解ける迷路 in C# DouKaku?

必ず解ける迷路

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

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

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

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

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

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

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


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

post comment

Posted feedbacks - C#

まだC#のコードがない様なので、遅すぎて恥ずかしいのを我慢して投稿します。

OS:Windows XP Home SP2 CPU:AMD Sempron 3400+ 1.99GHz メモリ:480MB

ファイルへの出力で15分から1時間位の間で変動するようです。

掘った方向をメモして枝切りすればもう少し速くなるかも。

see: 迷路自動生成アルゴリズム

//http://ja.doukaku.org/123/　投稿用
using System;
using System.Collections.Generic;
using System.Text;
class Program {
    static void Main(string[] args) {
        long tick = DateTime.Now.Ticks;
        const int X = 0;
        const int Y = 1;
        int xSize = int.Parse(args[0]);
        int ySize = int.Parse(args[1]);
        Random rnd = new Random();
        //注目点初期化
        int x = rnd.Next(0, xSize - 1) * 2 + 1;
        int y = rnd.Next(0, ySize - 1) * 2 + 1;
        List<int[]> canDigRoard = new List<int[]>();//注目点とすることが出来るセル
        bool[,] maze = new bool[xSize * 2 + 1, ySize * 2 + 1];//迷路データ　trueが道、falseが壁
        //全部壁にする
        for(int i = 0; i < maze.GetLength(X); i++) {
            for(int j = 0; j < maze.GetLength(Y); j++) {
                maze[i, j] = false;
            }
        }
        maze[x,y] = true;
        canDigRoard.Add(new int[] { x, y });
        //メインループ
        while(true) {
            int[][] directionList = new int[][] { 
                new int[] { -1, 0 }, 
                new int[] { 1, 0 }, 
                new int[] { 0, -1 }, 
                new int[] { 0, 1 } };
            int directionListLast = directionList.Length - 1;
            int[] direction;//方向
            do {
                int directionListIndex = rnd.Next(directionListLast);
                direction = directionList[directionListIndex];
                directionList[directionListIndex] = directionList[directionListLast--];
                if(maze.GetLength(X) > x + direction[X] * 2 && maze.GetLength(Y) > y + direction[Y] * 2 &&
                    x + direction[X] * 2 >= 0 && y + direction[Y] * 2 >= 0) {//インデックスが範囲内か判定
                    if(!(maze[x + direction[X] * 2, y + direction[Y] * 2])) {//2マス先が道かどうか
                        maze[x + direction[X], y + direction[Y]] = true;
                        maze[x + direction[X] * 2, y + direction[Y] * 2] = true;
                        canDigRoard.Add(new int[] { x + direction[X] * 2, y + direction[Y] * 2 });
                        break;
                    }
                }
            } while(directionListLast != -1);
            if(directionListLast == -1){
                for(int i = 0; i < canDigRoard.Count; i++) {
                    if(canDigRoard[i][X] == x && canDigRoard[i][Y] == y) {
                        canDigRoard.RemoveAt(i);
                    }
                }
                if(canDigRoard.Count == 0) break;
                int canDigRoardIndex = rnd.Next(0, canDigRoard.Count - 1);
                x = canDigRoard[canDigRoardIndex][X];
                y = canDigRoard[canDigRoardIndex][Y];
            } else {
                x += direction[X] * 2;
                y += direction[Y] * 2;
            }
        }
        string time = (DateTime.Now.Ticks - tick) / 10000L + "ms";
        //出力
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < maze.GetLength(Y); i++) {
            for(int j = 0; j < maze.GetLength(X); j++) {
                sb.Append(maze[j, i] ? "　" : "■");
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb + time);
        Console.ReadLine();
    }
}

悔しいので書き直しました。穴掘り法ですが、前のコードは前進出来なくなったときにランダムに戻ってましたが、掘った履歴を保存しているList<T>の、特にRemove()のパフォーマンスが悪いので Stack<T>に置き換えて、ランダムではなく一つ前に戻るようにしました。

引数に、画面に収まる迷路のサイズを指定して、 36、37行目の //Out(_maze, x, y); //System.Threading.Thread.Sleep(100); と 62行目の //Console.Clear(); のコメントを外すと、モグラﾀｿ(●)が掘っている様子をリアルタイムで表示します。w

OS:Windows XP Home SP2 CPU:AMD Sempron 3400+ 1.99GHz メモリ:480MB 迷路生成のみ　1171ms 出力こみ　1750ms(ファイルへ出力)

C#ﾀｿだってやれば出来る子なんですぅ！

using System;
using System.Collections.Generic;
using System.Text;

class Class1 {
    static void Main(string[] args) {
        long tick = DateTime.Now.Ticks;
        bool[,] maze = new bool[int.Parse(args[0]) * 2 + 3, int.Parse(args[1]) * 2 + 3];
        for(int y = 0; y < maze.GetLength(1); y++) {
            for(int x = 0; x < maze.GetLength(0); x++) {
                maze[x, y] = x == 0 || y == 0 || x == maze.GetLength(0) - 1 || y == maze.GetLength(1) - 1;
            }
        }
        モグラﾀｿ mogura = new モグラﾀｿ(maze);
        string time = (DateTime.Now.Ticks - tick) / 10000L + "ms";
        mogura.Out(maze);
        Console.WriteLine("迷路生成のみ　" + time);
        Console.Write("出力こみ　" + ((DateTime.Now.Ticks - tick) / 10000L) + "ms");
        Console.ReadLine();
    }
}

class モグラﾀｿ {
    Random rnd = new Random();
    bool[,] _maze;
    Stack<int[]> line;
    public モグラﾀｿ(bool[,] maze) {
        _maze = maze;
        line = new Stack<int[]>(_maze.Length);
        Dig(2, 2);
    }

    private void Dig(int x_, int y_) {
        int x = x_, y = y_;
        while(true) {
            //Out(_maze, x, y);
            //System.Threading.Thread.Sleep(100);
            _maze[x, y] = true;
            List<int[]> direcList = new List<int[]>();
            if(!_maze[x, y - 2]) direcList.Add(new int[] { 0, -1 });
            if(!_maze[x - 2, y]) direcList.Add(new int[] { -1, 0 });
            if(!_maze[x, y + 2]) direcList.Add(new int[] { 0, 1 });
            if(!_maze[x + 2, y]) direcList.Add(new int[] { 1, 0 });
            int[] direc;
            if(direcList.Count == 0) {
                if(line.Count == 0) break; ;
                int[] back = line.Pop();
                x = back[0];
                y = back[1];
                continue;
            } else if(direcList.Count == 1) direc = direcList[0];
            else direc = direcList[rnd.Next(0, direcList.Count)];

            _maze[x + direc[0], y + direc[1]] = true;
            x += direc[0] * 2;
            y += direc[1] * 2;
            line.Push(new int[] { x, y });
        }
    }
    
    private void Out(bool[,] maze, int x_, int y_) {
        //Console.Clear();
        StringBuilder sb = new StringBuilder();
        for(int y = 1; y < maze.GetLength(1) - 1; y++) {
            for(int x = 1; x < maze.GetLength(0) - 1; x++) {
                if(x_ == x && y_ == y) { 
                    sb.Append("●");
                } else {
                    sb.Append(maze[x, y] ? "　" : "■");
                }
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb);
    }
    public void Out(bool[,] maze) {
        Out(maze, -1, -1);
    }
}

無難に棒倒し法です。

CPU：Intel Core 2 Duo CPU 2.00GHz メモリ：2046MB OS：Windows Vista Home Basic

class Program
{
    static void Main(string[] args)
    {
        randomMeiro(1024, 1024);
        Console.ReadLine();
    }

    public static void randomMeiro(int m, int n)
    {
        //変数
        long start = DateTime.Now.Ticks;
        Random rand = new Random(DateTime.Now.Millisecond);
        n = 2 * n;
        m = 2 * m;

        //データ生成
        bool[,] map = new bool[n + 1, m + 1];
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= m; j++)
            {
                if (j == 0 || i == 0 || i == n || j == m || (i % 2 == 0 && j % 2 == 0) ) map[i, j] = true;
                else map[i, j] = false;
            }
        }

        //迷路生成
        for (int i = 2; i < n; i += 2)
        {
            for (int j = 2; j < m; j += 2)
            {
                int max = 2;
                if (i == 2) max++;
                int x = i;
                int y = j;
                switch (rand.Next(0, max))
                {
                    case 0: x++; break;
                    case 1: y++; break;
                    case 2: x--; break;
                    case 3: y--; break;
                }
                if (map[x, y]) j -= 2;
                else map[x, y] = true;
            }
        }
        Console.WriteLine("ファイル出力無：" + ((DateTime.Now.Ticks - start) / 10000L) + "ms");

        //表示
        using (StreamWriter sw = new StreamWriter(@"meiro.dat"))
        {
            for (int i = 0; i <= n; i++)
            {
                for (int j = 0; j <= m; j++)
                {
                    if (map[i, j]) sw.Write("■");
                    else sw.Write("　");
                }
                sw.WriteLine();
            }
        }

        Console.WriteLine("ファイル出力有：" + ((DateTime.Now.Ticks - start) / 10000L) + "ms");
    }
}

DouKaku?

必ず解ける迷路

Posted feedbacks - C#

Index

Feed

Other

Link

Pathtraq