DouKaku?beta

Comment detail

必ず解ける迷路 (Nested Flatten)
はじめまして、通りすがりです。

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

開発環境は、
・東芝のノート：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;
}

穴掘り法ですね。 迷路生成1秒ですか。さすがC++は速いなぁ。

VC++2005EEのコマンドラインで/EHscオプションを指定してコンパイル、実行したら時々こんな感じで掘り残しがあるのは仕様でしょうか？ 　■■■■■■■　■　■　■■■■■■■　■■ 　■　■　　　　　■　　　■　　　　　　　■ 　■　■　■■■■■■■■■　■■■■■■■■ 　　　■　　　　　　　　　■　■ 　■■■■■■■　■■■　■　■　■■■■■ 　■　　　■　■　　　■　　　■　■■■　■ ■■　■　■　■　■■■■■■■　■■■　■■ 　　　■　　　■　　　　　　　■ 　■■■■■　■■■■■　■　■■■■■■■ 　　　■　　　　　　　■　■　■ ■■　■　■■■■■　■■■　■　■■■■■■ 　■　■　■　　　　　■　　　■　■　■ 　■■■　■■■　■　■　■■■　■　■　■■ 　　　　　■　　　■　■　　　■　■　■ ■■　■■■■■　■■■　■　■　■　■■■■ 　　　■■■■■　■　　　■　■ ■■■■■■■■■■　■■■　■■■■■■■ 　　　　　　　　　　　■　■　■　　　　　■ 　■■■■■■■■■■■　■　■　■　■■■ (1024*1024の実行結果からコピペ)

VC++2005EEのコマンドラインで/EHscオプションを指定してコンパイル、実行したら時々こんな感じで掘り残しがあるのは仕様でしょうか？
　■■■■■■■　■　■　■■■■■■■　■■
　■　■　　　　　■　　　■　　　　　　　■　
　■　■　■■■■■■■■■　■■■■■■■■
　　　■　　　　　　　　　■　■　　　　　　　
　■■■■■■■　■■■　■　■　■■■■■　
　■　　　■　■　　　■　　　■　■■■　■　
■■　■　■　■　■■■■■■■　■■■　■■
　　　■　　　■　　　　　　　■　　　　　　　
　■■■■■　■■■■■　■　■■■■■■■　
　　　■　　　　　　　■　■　■　　　　　　　
■■　■　■■■■■　■■■　■　■■■■■■
　■　■　■　　　　　■　　　■　■　■　　　
　■■■　■■■　■　■　■■■　■　■　■■
　　　　　■　　　■　■　　　■　■　■　　　
■■　■■■■■　■■■　■　■　■　■■■■
　　　■■■■■　■　　　■　■　　　　　　　
■■■■■■■■■■　■■■　■■■■■■■　
　　　　　　　　　　　■　■　■　　　　　■　
　■■■■■■■■■■■　■　■　■　■■■　
(1024*1024の実行結果からコピペ)
ルール的には堀残しはNGです。

C++のコンパイル環境がないので実行して確認できませんが、バグがあるのかもしれませんね。

なんとなく、
 std::random_shuffle(U.Char,U.Char+4);
あたりが怪しそうです。
C++のコード追うのは苦手orz

お久しぶりです。 >>#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 このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]