DouKaku?beta

Comment detail

必ず解ける迷路 (Nested Flatten)

This comment is reply for 5377 あにす: VC++2005EEのコマンドラインで/...(必ず解ける迷路). Go to thread root. 

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