Artifact 561b82c7ab9e8ca630227cd0a012680494476943

• File SRM/146/1C.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <string>
#include <queue>
#include <algorithm>
using namespace std;

struct Roundabout
{
	int clearUpTime(string north, string east, string south, string west)
	{
		char        M[4] = {'N', 'E', 'S', 'W'};
		string      C[4] = {north, east, south, west};
		char        R[4] = {'-', '-', '-', '-'};
		queue<char> Q[4];

		int N = 0;
		for(int i=0; i<4; ++i)
			for(int j=0; j<C[i].size(); ++j)
				if( C[i][j] != '-' )
					++N;

		int t = 0;
		for( ;; ++t )
		{
			// leave
			for(int i=0; i<4; ++i)
				if( R[i] == M[i] )
					R[i] = M[i]-'A'+'a', --N; // put ghosts
			if( !N )
				return t;

			// rotate
			rotate( R+0, R+1, R+4 );

			// enter
			if( !Q[0].empty() && !Q[1].empty() && !Q[2].empty() && !Q[3].empty() )
			{
				if( R[0]=='-' )
					R[0] = Q[0].front(), Q[0].pop();
			}
			else
			{
				bool Go[] = {
					R[0]=='-' && Q[1].empty(),
					R[1]=='-' && Q[2].empty(),
					R[2]=='-' && Q[3].empty(),
					R[3]=='-' && Q[0].empty(),
				};
				for(int i=0; i<4; ++i)
					if( Go[i] && !Q[i].empty() )
						R[i] = Q[i].front(), Q[i].pop();
			}

			// clear ghost
			for(int i=0; i<4; ++i)
				if( 'a'<=R[i] && R[i]<='z' )
					R[i] = '-';

			// queue
			for(int i=0; i<4; ++i)
				if( t < C[i].size() && C[i][t]!='-' )
					Q[i].push( C[i][t] );
		}
	}
};