迷宮 2016 /5 / 26 /12:59

#include<bits/stdc++.h>
//#include"cksh.h"
using namespace std;
#define a first
#define b second
#define mp make_pair
const char U=' ',V='#';
const int H=23,W=49,CURL=2;///5(very) ～ 10(low)
const int base=5,range=20; ///for pace
const int pit_base=10,pit_range=10;
const int BCOL=15,WCOL=4,SCOL=10,TOP=1,BLANK=2;
const int INF=100000000,m[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
typedef pair<int,int> PII;
char p[H][W];
deque<int> way;
class pos
{
    public:
    int x;int y;
    bool equal(pos p)
    {
        return (this->x==p.x&&this->y==p.y)?true:false; ///要玩玩看嗎w why i can't type chinese你要改輸入法我用許是反正你改誠心注音喔喔喔
    }
};///= =好玩嗎成發作玩了 我還要把那個自動解的結果讓他會動 可能還要有個主畫面 就差這些 可以做多人遊戲 你突然開了一個很大的坑 pit 對吧所以要先做什麼 動畫好吧 我物理作業還沒寫= =
///我有兩題不太會寫空著 哪兩個 ?最後一題-2跟第九題 最後一題我會 第九題的畫 其實我還在找考卷 要圖嗎 我先找找 然後我發現我寶典不見了 悲劇
class MAKE_PIC
{
    public:

        bool solve_maze()
        {
            bfs();
            pos now,zero;now.x=H-2,now.y=W-2;zero.x=0;zero.y=0;
            while(!from[now.x][now.y].equal(now)&&!from[now.x][now.y].equal(zero))
            {
                walk.push_front(now);
                now=from[now.x][now.y];
            }
            if(walk.empty())return false;
            walk.push_front(now);
            for(int i=1;i<walk.size();i++)
            {
                for(int j=0;j<4;j++)
                {
                    now=walk[i-1];
                    now.x+=m[j][0];now.y+=m[j][1];
                    if(now.equal(walk[i]))way.push_back(j);
                }
            }
            way.push_front(2);
            way.push_back(2);
            for(int i=0;i<way.size();i++)
            {
                if(way[i]==0)printf("上");
                if(way[i]==1)printf("左");
                if(way[i]==2)printf("右");
                if(way[i]==3)printf("下");
            }
            printf("\n");
            walk.clear();
            //way.clear();
            return true;
        }
        void make_pic()
        {
            pre(),Build();
            while(check())reBuild(),Build();
        }
        void put()
        {
            for(int i=0;i<H;i++)
            {
                for(int j=0;j<W;j++)
                    printf("%c",p[i][j]);puts("");
            }
        }
        bool N_dig_hole(PII k)
        {
            if(p[k.a-1][k.b-1]!=V && p[k.a-1][k.b]!=V && p[k.a][k.b-1]!=V)return 1;
            if(p[k.a-1][k.b]!=V && p[k.a][k.b+1]!=V && p[k.a-1][k.b+1]!=V)return 1;
            if(p[k.a+1][k.b]!=V && p[k.a][k.b-1]!=V && p[k.a+1][k.b-1]!=V)return 1;
            if(p[k.a+1][k.b]!=V && p[k.a][k.b+1]!=V && p[k.a+1][k.b+1]!=V)return 1;
            return 0;
        }
        void dig_hole()
        {
            int pit=pit_base+rand()%pit_range;
            vector<PII> vd;
            for(int i=1;i<H-1;i++)
                for(int j=1;j<W-1;j++)
                    if(p[i][j]==V)vd.push_back(mp(i,j));
            while(pit-- && vd.size())
            {
                int q=rand()%(vd.size());
                PII now=vd[q];
                vd.erase(vd.begin()+q,vd.begin()+q+1);
                if(N_dig_hole(now))pit++;
                else p[now.a][now.b]=U;
            }
        }
    private:
    int step[H][W];
    pos from[H][W];
    deque<pos> Q,walk;
    void bfs()
    {
        for(int i=0;i<H;i++)
        {
            for(int j=0;j<W;j++)
            {
                step[i][j]=INF;
                from[i][j].x=0;
                from[i][j].y=0;
            }
        }
        pos A,B;A.x=1;A.y=1;
        step[1][1]=0;
        from[1][1].x=1;from[1][1].y=1;
        Q.push_back(A);
        while(!Q.empty())
        {
            A=Q.front();Q.pop_front();
            for(int i=0;i<4;i++)
            {
                B.x=A.x+m[i][0],B.y=A.y+m[i][1];
                if(p[B.x][B.y]==V)continue;
                if(step[A.x][A.y]+1>=step[B.x][B.y])continue;
                from[B.x][B.y]=A;
                step[B.x][B.y]=step[A.x][A.y]+1;
                Q.push_back(B);
            }
        }
    }
    vector<PII> v; /// what need to do
    PII st,en;
    int Z[4]={-1,0,1,0},X[4]={0,-1,0,1};
    void pre()
    {
        st=mp(1,0),en=mp(H-2,W-1);
        for(int i=0;i<H;i++)for(int j=0;j<W;j++)p[i][j]=U;
        for(int i=0;i<W;i++)p[0][i]=p[H-1][i]=V;
        for(int j=0;j<H;j++)p[j][0]=p[j][W-1]=V;
        p[st.a][st.b]=U,p[en.a][en.b]=U;
        p[0][0]=U,p[0][W-1]=U,p[H-1][0]=U,p[H-1][W-1]=U;
        for(int i=0;i<H;i++)
            for(int j=0;j<W;j++)
                if(i%2==0 && j%2==0 && p[i][j]==V)v.push_back(mp(i,j));
        p[0][0]=V,p[0][W-1]=V,p[H-1][0]=V,p[H-1][W-1]=V;
    }
    bool CAN_GO(PII now,int dir)
    {
        int x=now.a+Z[dir]*2,y=now.b+X[dir]*2;
        if(Z[dir]==0)return (p[x][y]!=V && p[x-1][y]!=V && p[x+1][y]!=V);
        return (p[x][y]!=V && p[x][y-1]!=V && p[x][y+1]!=V);
    }
    bool check()
    {
        for(int i=1;i<H-1;i++)
            for(int j=1;j<W-1;j++)
                if(p[i][j]==U && p[i-1][j]==U && p[i][j-1]==U && p[i-1][j-1]==U)return 1;
        return 0;
    }
    void reBuild()
    {
        for(int i=1;i<H-1;i++)
            for(int j=1;j<W-1;j++)
                if(i%2==0 && j%2==0 && p[i][j]==V )v.push_back(mp(i,j));
    }
    void Build()  /// 都是偶數可以轉彎
    {
        srand(time(NULL));
        while(v.size())
        {
            int q=rand()%((int)v.size()),dir,pace;
            PII now=v[q];
            v.erase(v.begin()+q,v.begin()+q+1);
            if(now.a==0)dir=2;
            else if(now.b==0)dir=3;
            else if(now.a==H-1)dir=0;
            else if(now.b==W-1)dir=1;
            else dir=rand()%4;
            pace=rand()%range+base;
            while(pace--)
            {
                if(CAN_GO(now,dir)==0)
                {
                    if(now.a%2==1 || now.b%2==1)break;
                    if(CAN_GO(now,(dir+1)%4))dir=(dir+1)%4;
                    else if(CAN_GO(now,(dir+3)%4))dir=(dir+3)%4;
                    else break;
                }
                now.a+=Z[dir],now.b+=X[dir],p[now.a][now.b]=V;
                if(!(now.a%2 || now.b%2))
                {
                    int x=rand()%CURL;
                    if(x==0)dir=(dir+1)%4;
                    else if(x==1)dir=(dir+3)%4;
                }
            }
        }
    }
};

//void show_maze()
//{
//  for(int i=0;i<H;i++)
//  {
//      for(int j=0;j<W;j++)
//      {
//          if(p[i][j]==U)
//          {
//              SetColor(0,BCOL);
//              printf("　");
//          }
//          if(p[i][j]==V)
//          {
//              SetColor(0,WCOL);
//              printf("　");
//          }
//      }
//      printf("\n");
//  }
//  SetColor(15,0);
//  gotoxy(TOP+1,W*2+BLANK);
//    printf("高度: %d 寬度: %d",H,W);
//    gotoxy(TOP+2,W*2+BLANK);
//    printf("使用步數: 0");
//}
//
//void edit_step(int s)
//{
//  SetColor(15,0);
//    gotoxy(TOP+2,W*2+BLANK);
//    printf("使用步數: %d",s);
//}
//
//void print_box(int x, int y,int col)
//{
//  SetColor(0,col);
//  gotoxy(x,y*2);
//  printf("　");
//}
//
//void user_play()
//{
//  int nx=1,ny=0,s=0;
//  clrscr();
//  show_maze();
//  print_box(nx,ny,SCOL);
//  while(!(nx==(H-2)&&ny==(W-1)))
//  {
//      if(kbhit())
//      {
//          int w=getkey();
//          if(p[nx+m[w][0]][ny+m[w][1]]==U)
//          {
//              print_box(nx,ny,BCOL);
//              nx+=m[w][0],ny+=m[w][1];
//              print_box(nx,ny,SCOL);
//              edit_step(++s);
//          }
//      }
//      SetColor(15,0);
//  }
//  gotoxy(H+1,0);
//  printf("YOU WIN\n");
//}
//
//void pc_play()
//{
////    for(int i=0;i<way.size();i++)printf("%d",way[i]);
////    getchar();
//    int nx=1,ny=0,s=0;
//  clrscr();
//  show_maze();
//  print_box(nx,ny,SCOL);
//  while(!(nx==(H-2)&&ny==(W-1)))
//  {
//      Sleep(200);
//        int w=way.front();way.pop_front();
//        print_box(nx,ny,BCOL);
//      nx+=m[w][0],ny+=m[w][1];
//      print_box(nx,ny,SCOL);
//      edit_step(++s);
//      SetColor(15,0);
//  }
//  gotoxy(H+1,0);
//  printf("YOU WIN\n");
//}
int main()
{
    MAKE_PIC maze;
    maze.make_pic();
    maze.put();
//    maze.solve_maze();
    maze.dig_hole();
    maze.put();
    maze.solve_maze();
//    user_play();
    return 0;
}