DouKaku? 5374 あにす: 悔しいので書き直しました。穴掘り法で...(必ず解ける迷路)

Comment detail

悔しいので書き直しました。穴掘り法ですが、前のコードは前進出来なくなったときにランダムに戻ってましたが、掘った履歴を保存している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);
    }
}

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq