FragileMirrors.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <ctime>
#include <set>

using namespace std;



//  vector出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

//  Xor Shift
unsigned int xor128(void){
    static unsigned int x=123456789, y=362436069, z=521288629, w=88675123;
    unsigned int t=x^(x<<11); x=y; y=z; z=w;
    return w=(w^(w>>19))^(t^(t>>8));
}



class Board
{
public:
    int         N;
    char        C[100*100];
    char        C2[100*100+100];
    int         J[4*100*100+4*100];
    unsigned int H[4*100*100];
    int         Hp;
    vector<int> EN;
    int         step;

    Board( vector<string> B )
    {
        N = (int)B.size();

        for ( int y=0; y<N; y++ )
        for ( int x=0; x<N; x++ )
            C[y*N+x] = B[y][x];

        for ( int i=0; i<N*N; i++ )
            C2[i] = C[i]=='L' ? 3 : 1;
        for ( int i=N*N; i<N*N+N; i++ )
            C2[i] = 0;

        for ( int y=0; y<N; y++ )
        for ( int x=0; x<N; x++ )
        for ( int d=0; d<4; d++ )
        {
            int tx = x;
            int ty = y;
            int td;
            if ( C[y*N+x]=='L' )
            {
                switch ( d )
                {
                case 0: tx--; td=1; break;
                case 1: ty++; td=0; break;
                case 2: tx++; td=3; break;
                case 3: ty--; td=2; break;
                }
            }
            else
            {
                switch ( d )
                {
                case 0: tx++; td=3; break;
                case 1: ty--; td=2; break;
                case 2: tx--; td=1; break;
                case 3: ty++; td=0; break;
                }
            }

            int t = (ty*N+tx)*4+td;
            if ( ty<0 ) t = 4*N*N + tx;
            if ( tx>=N ) t = 4*N*N + N + ty;
            if ( ty>=N ) t = 4*N*N + 2*N + N-tx-1;
            if ( tx<0 ) t = 4*N*N + 3*N + N-ty-1;

            J[(y*N+x)*4+d] = t;
        }
        for ( int x=0; x<N; x++ )
            J[4*N*N+x] = 4*x;
        for ( int y=0; y<N; y++ )
            J[4*N*N+N+y] = 4*(y*N+N-1)+1;
        for ( int x=0; x<N; x++ )
            J[4*N*N+2*N+N-x-1] = 4*((N-1)*N+x)+2;
        for ( int y=0; y<N; y++ )
            J[4*N*N+3*N+N-y-1] = 4*(y*N)+3;

        Hp = 0;

        EN.clear();

        step = 0;
    }

    bool check( int s ) const
    {
        return J[s+4*N*N]<4*N*N;
    }

    int lase( int s )
    {
        int N = this->N;
        int e = 0;

        for ( int p=J[s+4*N*N]; p<4*N*N; p=J[p] )
        {
            for ( int d=0; d<4; d++ )
            {
                int t = J[p/4*4+d];

                t ^= C2[t/4];
                //if ( t<4*N*N )
                //  t ^= C[t/4]=='L' ? 3 : 1;
                
                H[Hp++] = (unsigned int)t<<16|J[t];

                J[t] = J[p/4*4+(d+2)%4];
            }
            e++;
        }

        EN.push_back(e*4);

        step++;

        return e;
    }

    void undo()
    {
        step--;

        int e = EN.back(); EN.pop_back();

        for ( int i=0; i<e; i++ )
        {
            unsigned int h = H[--Hp];
            J[h>>16] = h&0xffff;
        }
    }

    vector<int> p2v( int p ) const
    {
        vector<int> v;
        if ( p<N ) v.push_back(-1), v.push_back(p);
        else if ( p<2*N ) v.push_back(p-N), v.push_back(N);
        else if ( p<3*N ) v.push_back(N), v.push_back(N-(p-2*N)-1);
        else if ( p<4*N ) v.push_back(N-(p-3*N)-1), v.push_back(-1);
        return v;
    }

    vector<int> p2v( vector<int> p ) const
    {
        vector<int> v;
        for ( int i=0; i<(int)p.size(); i++ )
        {
            vector<int> t = p2v(p[i]);
            v.push_back( t[0] );
            v.push_back( t[1] );
        }
        return v;
    }

    string tostring() const 
    {
        string s = "";
        for ( int y=0; y<N; y++ )
        {
            for ( int x=0; x<N; x++ )
                s += C[y*N+x];
            s += "\n";
        }
        return s;
    }
};



vector<int> naive( Board *B, int limit=9999 )
{
    vector<int> r;

    while ( true )
    {
        if ( (int)r.size()>=limit )
            break;

        int m = 0;
        int mp;

        for ( int p=0; p<B->N*4; p++ )
        if ( B->check(p) )
        {
            int t = B->lase(p);
            if( t>m )
                m = t,
                mp = p;
            B->undo();
        }
        if ( m==0 )
            break;
        B->lase(mp);
        r.push_back(mp);
    }

    for ( int i=0; i<(int)r.size(); i++ )
        B->undo();

    return r;
}



class FragileMirrors {
public: vector<int> destroy( vector<string> board )
{
    clock_t start = clock();
    clock_t current;
    int TL = 9*CLOCKS_PER_SEC;

    Board B(board);

    vector<int> p = naive(&B);

    for ( int step=0; ; step++ )
    {
        if ( step%100==0 )
            current = clock();

        int e = current-start;

        if ( e>=TL )
            break;

        int r;
        int l = p.size();
        if ( e<TL*1/2 )
            r = xor128()%(l/4);
        else if ( e<TL*3/4 )
            r = xor128()%(l/4)+l/4;
        else
            r = xor128()%(l/2)+l/2;
        
        vector<int> t = p;
        t.resize(r);
        for ( int i=0; i<(int)r; i++ )
            B.lase(t[i]);

        int m;
        do m=xor128()%(4*B.N);
        while ( !B.check(m) );
        
        t.push_back(m);
        B.lase(m);

        vector<int> t2 = naive( &B, p.size()-t.size() );
        t.insert(t.end(),t2.begin(),t2.end());

        B.undo();
        for ( int i=0; i<(int)r; i++ )
            B.undo();

        if ( t.size() < p.size() )
            p = t;
    }

    return B.p2v(p);    
}
};

#ifdef LOCAL

void test()
{
    FragileMirrors fm;

    srand(123);

    double sum = 0;

    for ( int i=0; i<10; i++ )
    {
        int N = rand()%51+50;
        vector<string> S(N,string(N,' '));
        for ( int y=0; y<N; y++ )
        for ( int x=0; x<N; x++ )
            S[y][x] = rand()%2==0 ? 'L' : 'R';

        clock_t start = clock();
        int r = (int)(fm.destroy(S).size()/2);
        
        printf( "%3d %3d %.8f %4.2f\n", N, r, (double)N/r, (double)(clock()-start)/CLOCKS_PER_SEC );

        sum += (double)N/r;
    }
    printf( "%.8f\n", sum/10 );
}


int main()
{
    //test();

    FragileMirrors fm;

    int N; cin>>N;
    vector<string> board(N);
    for ( int i=0; i<N; i++ )
        cin>>board[i];

    vector<int> ret = fm.destroy(board);

    cout<<ret.size()<<endl;
    for ( int i=0; i<(int)ret.size(); i++ )
        cout<<ret[i]<<endl;

    fprintf( stderr, "N = %d\n", N );
    fprintf( stderr, "%.3f [s]\n", (double)clock()/CLOCKS_PER_SEC );

    return 0;
}

#endif