DouKaku?beta

challenge 必ず解ける迷路 

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

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

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

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

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

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

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


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

Posted feedbacks - C++

はじめまして、通りすがりです。

懐かしいお題だったので、勢いで作ってみました。一応、テストはしましたけど、まだバグってるかも知れません。

開発環境は、
・東芝のノート：AX/530LL＋Mem512（=７０４位）・VC＋＋２００８　Express（C++＆STL）・6時間くらいの時間。

実行環境。
・上記の機材。・速度向け最適化。・リリースビルド。
＝＞ファイルにリダイレクトで3秒位でした。迷路の生成自体は1秒ちょいってとこじゃないでしょうか。
えぇーっと、ライブラリが良いのと、ネーティブコードなのでアドバンテージとれてるかもしれないです。

注意ですけど、最初にがーっとメモリ取るので環境によってはあんまり好ましくない動作をするかもしれません。ウチでは大丈夫というのはあてになりませんので。。。

長くなりましたけど、面白かったです。 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <stdexcept>
class Maze_t{
    typedef unsigned short MazeElement;
    typedef std::vector<MazeElement> maze_t;
    int Width_,Height_;
    maze_t Data;
    struct Point2{
        int x,y;
        void ToZero(){x=y=0;}
        void Set(int x_, int y_){x=x_; y=y_;}
    };
    
public:
    enum Flags{
        Left=0,
        Up,
        Right,
        Down,
        Visit,
    };
    Maze_t(size_t W,size_t H){
        Create(W,H);
    }
    void Create(size_t W,size_t H){
        Destroy();
        Width_=W;Height_=H;
        Data.resize(W*H);
        std::fill(Data.begin(),Data.end(),int(0));
        Generate();
    }
    void Destroy(){
        Data.clear();
        Width_ = 0;Height_= 0;
    }
    int Width(){ return Width_;}
    int Height(){ return Height_;}
    MazeElement WallInfo(int x, int y){
        if(!CanVisit(x,y)) return 0; 
        return GetElement(x,y);
    }
protected:
    bool CanVisit(int x, int y){
        if(x<0) return false;
        if(y<0) return false;
        if(Width()<=x) return false;
        if(Height()<=y) return false;
        return true;
    }
    bool AlreadyVisit(int x,int y){
        if(!CanVisit(x,y)) return true;
        return GetElement(x,y)>>Visit & 1;
    }
    void MarkVisit(int x,int y){
        if(CanVisit(x,y) == false) return;
        MazeElement& Me = GetElement(x,y);
        Me = Me | 1 << Visit;
    }
    MazeElement& GetElement(int x,int y){
        return Data[Width()*y+x];
    }
    void EraseWall(Point2 Base,Point2 To,int command){
        char Flg1[] = {Left,Up,Right,Down};
        char Flg2[] = {Right,Down,Left,Up};
        MazeElement* p;
        p = &(GetElement(Base.x,Base.y));
        (*p) = (*p) | (1<<Flg1[command]);
        p = &(GetElement(Base.x+To.x,Base.y+To.y));
        (*p) = (*p) | (1<<Flg2[command]);
    }
    struct Uni{
        union{
            int Int;
            char Char[4];
        };
    };
    void Generate(){//メモリ等確保後に実行しないと不整合起こします。つまり単体で使用しないでください。Create関数がエントリです。
        Point2 V[]={{-1,0},{0,1},{1,0},{0,-1}};
        Point2 T={rand()%Width(),rand()%Height()};
        std::vector<Point2> pov;
        std::vector<int> command;
        std::vector<int> rotate;
        Uni U;
        U.Int = 0x03020100;
        std::random_shuffle(U.Char,U.Char+4);
        int i=0;
        pov.push_back(T);
        command.push_back(i);
        rotate.push_back(U.Int);
        MarkVisit(T.x,T.y);
        while(pov.size() != 0){
            T = pov.back();
            i = command.back();
            U.Int = rotate.back();
            for(;i<4;i++){
                if(CanVisit(T.x+V[ U.Char[i]].x,T.y+V[ U.Char[i]].y)){
                    if(AlreadyVisit(T.x+V[ U.Char[i]].x,T.y+V[ U.Char[i]].y)) continue;
                    MarkVisit(T.x+V[ U.Char[i]].x,T.y+V[ U.Char[i]].y);
                    EraseWall(T,V[ U.Char[i]], U.Char[i]);
                    T.x=T.x+V[ U.Char[i]].x;
                    T.y=T.y+V[ U.Char[i]].y;
                    pov.push_back(T);
                    command.push_back(i);
                    rotate.push_back(U.Int);
                    i=0;
                    std::random_shuffle(U.Char,U.Char+4);
                }
            }
            pov.pop_back();
            command.pop_back();
            rotate.pop_back();
        }
    }
};
void PrintMaze(Maze_t& M){
    char W='W',R=' ';
    for(int i=0;i<M.Height();i++){
        for(int k=0;k<3;k++){
            for(int j=0;j<M.Width();j++){
                int wall = M.WallInfo(j,i);
                if(k==0) printf("%c%c%c",W, ((wall>>M.Down)&1)? R:W, W);
                if(k==1) printf("%c%c%c",((wall>>M.Left)&1)? R:W, ((wall>>M.Visit)&1)? R:W, ((wall>>M.Right)&1)? R:W);
                if(k==2) printf("%c%c%c",W, ((wall>>M.Up)&1)? R:W, W);            
            }
            puts("");
        }
    }
}
void PrintMaze2(Maze_t& M){
    char *W="■",*R="　";
    for(int j=0;j<M.Width();j++) printf("%s%s",W,W);
    puts(W);
    for(int i=0;i<M.Height();i++){
        for(int k=1;k<3;k++){
            printf("%s",W);
            for(int j=0;j<M.Width();j++){
                int wall = M.WallInfo(j,i);
                if(k==0) printf("%s%s", ((wall>>M.Down)&1)? R:W, W);
                if(k==1) printf("%s%s", ((wall>>M.Visit)&1)? R:W, ((wall>>M.Right)&1)? R:W);
                if(k==2) printf("%s%s", ((wall>>M.Up)&1)? R:W, W);            
            }
            puts("");
        }
    }
}
int main(){
    //srand(100);
    srand(time(NULL));
    Maze_t m(12,6);
    //Maze_t m(1024,1024);
    PrintMaze2(m);
    return 0;
}

このアルゴリズムで組んでみました。Pentium2 266MHzで30秒です。きっともっと最適化の余地があることでしょう。。。。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstdlib> // random, srand
#include <cassert> // assert
#include <ctime> // time

#define REP(i, b, e) for (size_t i = b; i < e; ++i)
#define STEP(i, b, e, step) for (size_t i = b; i < e; i += step)

const size_t wall = static_cast<size_t>(-1);

bool random()
{
    return std::rand() < RAND_MAX / 2;
}

void print(std::ostream& out, const std::vector<size_t>& map)
{
    REP(i, 0, map.size())
    {
        out << (map[i] == wall ? "¡" : "@");
    }

    out << std::endl;
}

void create_maze(const char* path, size_t n, size_t m)
{
    assert(n >= 1); assert(m >= 1);

    std::ofstream out(path);

    std::vector<size_t> areas(n); // identifers of areas

    REP(i, 0, n) areas[i] = i;

    std::vector<size_t> map(2 * n + 1, wall);

    print(out, map);

    for (--m; ; --m)
    {
        STEP(i, 1, 2 * n, 2) if (map[i] == wall)
        {
            assert(! areas.empty());

            map[i] = areas.back();

            areas.pop_back();
        }

        STEP(i, 2, 2 * n, 2) if (map[i - 1] != map[i + 1] && (m == 0 || random()))
        {
            const size_t old_area = map[i - 1];

            const size_t new_area = map[i + 1];

            areas.push_back(old_area);

            std::replace(map.begin(), map.end(), old_area, new_area); // caution! passed by reference

            map[i] = new_area;
        }

        print(out, map);

        if (m == 0)
        {
            break;
        }

        STEP(i, 2, 2 * n, 2)
        {
            map[i] = wall;
        }

        std::vector<size_t> count(n, 0);

        STEP(i, 1, 2 * n, 2)
        {
            ++count[map[i]];
        }

        STEP(i, 1, 2 * n, 2) if (count[map[i]] >= 2 && random())
        {
            --count[map[i]]; map[i] = wall;
        }

        print(out, map);
    }

    print(out, std::vector<size_t>(2 * n + 1, wall));
}

int main()
{
    std::srand(std::time(NULL));

    create_maze("result.txt", 1024, 1024);
}


C++, Pentium2 266MHzで30秒ですか。

私の使ったPentiumM 2100MHzとの性能差を約10倍とすると。
(クロック差8倍とメモリとかキャッシュとかで+2倍)
13秒ぐらいで生成できそうなんですが・・・。

あ、そういえば速度を計ったときには出力コードをコメント
にしてました。

純粋にバッファ操作の時間だけ計測すると何秒ぐらいになり
ますか？
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// こんな感じで。
void print(std::ostream& out, const std::vector<size_t>& map)
{
    REP(i, 0, map.size())
    {
//      out << (map[i] == wall ? "■" : "　");
    }

//  out << std::endl;
}

お久しぶりです。 >>#5377 はバグです。 実は投稿してから気がついて修正したんですけど、鮮度に欠ける時期だったので見送っていました。 でも、ちょっと後悔したので、当時FIXしたコードを乗っけます。 生成部分が幾らかコンパクトになっています。 ついでに、さっき追加で生成時間を計れるようにしました。

VC2008のリリースの速度最適化でコンパイルして1024*1024を６００クロック位で生成していました。

当時の事は大分忘れているので、もう修正できません。コッソリと後悔を埋めさせてもらいます。自己満足でごめんなさい。失礼しました。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <stdexcept>
class Maze_t{
    typedef unsigned short MazeElement;
    typedef std::vector<MazeElement> maze_t;
    int Width_,Height_;
    maze_t Data;//紛らわしいな。。。
    struct Point2{
        int x,y;
        void ToZero(){x=y=0;}
        void Set(int x_, int y_){x=x_; y=y_;}
        Point2 operator + (Point2& in){
            Point2 T;
            T.x= x+in.x;
            T.y= y+in.y;
            return T;
        }
    };
    
public:
    enum Flags{
        Left=0,
        Up,
        Right,
        Down,
        Visit,
    };
    Maze_t(size_t W,size_t H){
        Create(W,H);
    }
    void Create(size_t W,size_t H){
        Destroy();
        Width_=W;Height_=H;
        Data.resize(W*H);
        std::fill(Data.begin(),Data.end(),int(0));
        Generate();
    }
    void Destroy(){
        Data.clear();
        Width_ = 0;Height_= 0;
    }
    int Width(){ return Width_;}
    int Height(){ return Height_;}
    MazeElement WallInfo(int x, int y){
        if(!CanVisit(x,y)) return 0; 
        return GetElement(x,y);
    }
protected:
    bool CanVisit(int x, int y){
        if(x<0) return false;
        if(y<0) return false;
        if(Width()<=x) return false;
        if(Height()<=y) return false;
        return true;
    }
    bool AlreadyVisit(int x,int y){
        if(!CanVisit(x,y)) return true;
        return GetElement(x,y)>>Visit & 1;
    }
    void MarkVisit(int x,int y){
        if(CanVisit(x,y) == false) return;
        MazeElement& Me = GetElement(x,y);
        Me = Me | 1 << Visit;
    }
    MazeElement& GetElement(int x,int y){
        return Data[Width()*y+x];
    }
    void EraseWall(Point2 Base,Point2 To,int command){
        char Flg1[] = {Left,Up,Right,Down};
        char Flg2[] = {Right,Down,Left,Up};
        MazeElement* p;
        p = &(GetElement(Base.x,Base.y));
        (*p) = (*p) | (1<<Flg1[command]);
        p = &(GetElement(Base.x+To.x,Base.y+To.y));
        (*p) = (*p) | (1<<Flg2[command]);
    }
    struct Uni{
        union{
            int Int;
            char Char[4];
        };
    };
    void Generate(){
        Point2 T={rand()%Width(),rand()%Height()};
        Generate(T);
    }
    
    void Generate(Point2 Pos,bool IsDifferent = false){//非再起版。
        static Point2 V[]={{-1,0},{0,1},{1,0},{0,-1}};
        Uni F;
        F.Int=0x03020100;
        std::vector<Point2> stp;//スタック。
        stp.push_back(Pos);
        std::random_shuffle(F.Char,F.Char+4);
        while(stp.size() != 0){
            Pos = stp.back();stp.pop_back();
            if(!IsDifferent) F.Int=0x03020100;
            std::random_shuffle(F.Char,F.Char+4);
                for(int i=0;i<4;i++){
                    if(ToVisit(Pos,V[F.Char[i]],F.Char[i])) stp.push_back(Pos +V[F.Char[i]]);
                }
        }
        return ;
    }
    
    bool ToVisit(Point2 Base,Point2 To,int Command){
        if(!CanVisit(Base.x,Base.y)) return false;
        if(!CanVisit(Base.x+To.x,Base.y+To.y)) return false;
        //if(AlreadyVisit(Base.x,Base.y)) return false;
        if(AlreadyVisit(Base.x+To.x,Base.y+To.y)) return false;
        MarkVisit(Base.x,Base.y);
        MarkVisit(Base.x+To.x,Base.y+To.y);
        EraseWall(Base,To,Command);
        return true;
    }
};
void PrintMaze(Maze_t& M){
    char W='W',R=' ';
    for(int i=0;i<M.Height();i++){
        for(int k=0;k<3;k++){
            for(int j=0;j<M.Width();j++){
                int wall = M.WallInfo(j,i);
                if(k==0) printf("%c%c%c",W, ((wall>>M.Down)&1)? R:W, W);
                if(k==1) printf("%c%c%c",((wall>>M.Left)&1)? R:W, ((wall>>M.Visit)&1)? R:W, ((wall>>M.Right)&1)? R:W);
                if(k==2) printf("%c%c%c",W, ((wall>>M.Up)&1)? R:W, W);            
            }
            puts("");
        }
    }
}
void PrintMaze2(Maze_t& M){
    char *W="■",*R="　";
    for(int j=0;j<M.Width();j++) printf("%s%s",W,W);
    puts(W);
    for(int i=0;i<M.Height();i++){
        for(int k=1;k<3;k++){
            printf("%s",W);
            for(int j=0;j<M.Width();j++){
                int wall = M.WallInfo(j,i);
                if(k==0) printf("%s%s", ((wall>>M.Down)&1)? R:W, W);
                if(k==1) printf("%s%s", ((wall>>M.Visit)&1)? R:W, ((wall>>M.Right)&1)? R:W);
                if(k==2) printf("%s%s", ((wall>>M.Up)&1)? R:W, W);            
            }
            puts("");
        }
    }
}
int main(){
    //srand(100);
    srand(time(NULL));
    clock_t start,end;
    start = clock();
    //Maze_t m(12,5);
//    Maze_t m(19,11);
//    Maze_t m(19,100);
    Maze_t m(1024,1024);
    end = clock();
    printf("Generate at [%d]clock!\n",end-start);
    PrintMaze2(m);
    return 0;
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]