#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include  <deque>
#include <list>
#define _SIZE_ 30
#define _SET_ cout<<"\033[?25l\033[0m"
static int flags = 0;

typedef int Array[_SIZE_][_SIZE_]; 
using namespace std;

struct Pos
{
    int x;
    int y;
    Pos(int X,int Y):x(X),y(Y){}
};

class Grial
{
    public:
    Grial(Array a)
    {
        for(int i=0;i<_SIZE_;i++)
        {
            for(int j=0;j<_SIZE_;j++)
            {
                ar[i][j] = a[i][j];
            }
        }
    }
    void Init(Pos start)
    {
        int i = 0;
        int j = 0;
        char ch;
    deque<Pos> Q;
    list<Pos> Mlist;
    ar[start.x][start.y]    = 1;
    Q.push_front(start);
    while(1)
        {
      system("stty raw -echo");//改变终端控制，
      //输入一个字符就立刻相应，将原来的\n作为结束的标志，
      //改为输入一个字符就立即返回。
        ch = getchar();
        system("stty -raw echo");
        //让终端变回正常。
        switch(ch)
        {
            case 'w':
                stateUp(Q);         
            system("clear");
            Printf();
                    break;
            case 'a':
                stateLeft(Q);
                system("clear");
                Printf();
                    break;
            case 'd':
                stateRight(Q);
                system("clear");
                Printf();
                    break;  
            case 's':
                stateDown(Q);
                system("clear");
                Printf();
                    break;
            default:
                if(ch=='0')
                    exit(1);
        }
          GrialM(Mlist);
            if(flags==0)
            {
            Pos pos = AdancePoint(Mlist);
        ar[pos.x][pos.y] = 1;//随机点。
            flags=1;
            }
          sleep(0.675); 
        }
    }

bool IsIn(Pos pos,deque<Pos> &Q)
{
    deque<Pos> :: iterator it=Q.begin();
    while(it!=Q.end())
    {
        if(pos.x==it->x && pos.y==it->y)
            return true;
        it++;
    }
    return false;
}

void GrialM(list<Pos> &Mlist)//构造随机链表.
{
    for(int i=0;i<_SIZE_;i++)
    {
        for(int j=0;j<_SIZE_;j++)
        {
            if(ar[i][j]==0)
            Mlist.push_back(Pos(i,j));
        }
    }
}

Pos AdancePoint(list<Pos> &Mlist)
{
    int n = Mlist.size();
    list<Pos> :: iterator it = Mlist.begin();
    advance(it,rand()%n);
    return Pos(it->x,it->y);
}

void stateUp(deque<Pos> &Q)
    {
        Pos pos = Q.front();
        int x ;
        if(pos.x==0)
        {   x = _SIZE_-1;}
        else
        {x = pos.x-1;}
        int y = pos.y;
    Pos result(x,y);
    if(IsIn(result,Q))
    {
            exit(-1);
    }
        if(ar[x][y]==1)
        {
            Q.push_front(result);       
            flags=0;
            return ;
        }
        ar[x][y] = 1;
        Q.push_front(result);   

    Pos ret = Q.back();
        ar[ret.x][ret.y] = 0;
        Q.pop_back();
    }
    void stateLeft(deque<Pos> &Q)
    {
        Pos pos = Q.front();
        int x = pos.x;
        int y;
        if(pos.y==0)
        {   
            y = _SIZE_-1;
        }
        else{y = pos.y-1;}
        Pos result(x,y);
        if(IsIn(result,Q))
        {
            exit(-1);
        }
        if(ar[x][y]==1)
        {
            Q.push_front(result);
            flags=0;
            return ;
        }
        ar[x][y] = 1;
        Q.push_front(result);
        Pos ret = Q.back();
        ar[ret.x][ret.y] = 0;
        Q.pop_back();
    }
    void stateRight(deque<Pos> &Q)
    {
        Pos pos = Q.front();
        int x = pos.x;
        int y ;
        if(pos.y==_SIZE_-1)
        {
            y=0;
        }   
        else {y=pos.y+1;}
        Pos result(x,y);
        if(IsIn(result,Q))
        {
            exit(-1);
        }
        if(ar[x][y]==1)
        {
            Q.push_front(result);
            flags=0;
            return ;
        }
        ar[x][y] = 1;
        Q.push_front(result);
        Pos ret = Q.back();
        ar[ret.x][ret.y] = 0;
        Q.pop_back();
    }
    void stateDown(deque<Pos> &Q)
    {
        Pos pos = Q.front();
        int x ;
        if(pos.x==_SIZE_-1)
            {x=0;}
        else {x = pos.x+1;}
        int y = pos.y;
        Pos result(x,y);
        if(IsIn(result,Q))
        {
            exit(-1);
        }
        if(ar[x][y]==1)
        {   
            Q.push_front(result);
            flags=0;
            return ;
        }
        ar[x][y] = 1;
        Q.push_front(result);
        Pos ret = Q.back();
        ar[ret.x][ret.y] = 0;
        Q.pop_back();
    }
    public:
    void Printf()
    {
        _SET_;
        for(int i=0;i<_SIZE_;i++)
        {
            for(int j=0;j<_SIZE_;j++)
            {
                if(ar[i][j]==1)
                    {
                    cout<<"\033[34m1\033[0m ";
                    }
                else
                    cout<<ar[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    private:
    Array ar;
};
int main()
{
    Array arr={0};
    Grial gl(arr);
    int x = rand()%10;
    int y = rand()%10;
    Pos start(x,y);
    gl.Init(start);
}