2014年10月3日 星期五

2014/10/2 TopCoder SRM 146 Div1 800 Roundabout

/*
    麻煩的實作題 要注意細節
    不然會 debug很久 Q____Q
*/
// http://community.topcoder.com/stat?c=problem_statement&pm=1605&rd=4535
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>

using namespace std;

queue<int> E[4];
int P[4], _P[4];
string s[4];
bool B[4];

map<char, int> m;


struct Roundabout
{
    int clearUpTime(string north, string east, string south, string west)
    {
        fill(P, P+4, -1);

        s[0] = north; s[1] = west;
        s[2] = south; s[3] = east;

        m['N'] = 0; m['W'] = 1;
        m['S'] = 2; m['E'] = 3;

        int n = 0;

        for(int i = 0; i < 4; i++)
            n = max(n, (int)s[i].size());

        int clk = 0, _clk = 0;

        while(1)
        {

            bool f = false;

            for(int i = 0; i < 4; i++)
            {
                if( P[i] != i ) _P[(i+1)%4 ] = P[i];
                else _P[(i+1)%4 ] = -1;

                if( P[i] != -1 ) f = true;
            }

            bool f2 = true;

            for(int i = 0; i < 4; i++)
                B[i] = E[i].empty();

            for(int i = 0; i < 4; i++)
            {
                if( B[(i+3)%4] && P[(i+3)%4] == -1 && !E[i].empty() )
                {
                    f = true;
                    _P[i] = E[i].front();
                    E[i].pop();
                }
                if( B[(i+3)%4] ) f2 = false;
            }

            if( f2 )
                if( P[3] == -1 && !E[0].empty() )
                {
                    f = true;
                    _P[0] = E[0].front();
                    E[0].pop();
                }

            for(int i = 0; i < 4; i++)
                if( _clk < s[i].size() && s[i][_clk] != '-' )
                {
                    f = true;
                    E[i].push(m[s[i][_clk] ]);
                }

            for(int i = 0; i < 4; i++)
                P[i] = _P[i];

            if( f ) clk = _clk;
            else if( _clk > n ) break;
            _clk++;


        }

        return clk;
    }
};

沒有留言:

張貼留言