4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: struct Roundabout
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	int clearUpTime(string north, string east, string south, string west)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		char        M[4] = {'N', 'E', 'S', 'W'};
4fd800b3a8 2011-02-23        kinaba: 		string      C[4] = {north, east, south, west};
4fd800b3a8 2011-02-23        kinaba: 		char        R[4] = {'-', '-', '-', '-'};
4fd800b3a8 2011-02-23        kinaba: 		queue<char> Q[4];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		int N = 0;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<4; ++i)
4fd800b3a8 2011-02-23        kinaba: 			for(int j=0; j<C[i].size(); ++j)
4fd800b3a8 2011-02-23        kinaba: 				if( C[i][j] != '-' )
4fd800b3a8 2011-02-23        kinaba: 					++N;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		int t = 0;
4fd800b3a8 2011-02-23        kinaba: 		for( ;; ++t )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			// leave
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i<4; ++i)
4fd800b3a8 2011-02-23        kinaba: 				if( R[i] == M[i] )
4fd800b3a8 2011-02-23        kinaba: 					R[i] = M[i]-'A'+'a', --N; // put ghosts
4fd800b3a8 2011-02-23        kinaba: 			if( !N )
4fd800b3a8 2011-02-23        kinaba: 				return t;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			// rotate
4fd800b3a8 2011-02-23        kinaba: 			rotate( R+0, R+1, R+4 );
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			// enter
4fd800b3a8 2011-02-23        kinaba: 			if( !Q[0].empty() && !Q[1].empty() && !Q[2].empty() && !Q[3].empty() )
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				if( R[0]=='-' )
4fd800b3a8 2011-02-23        kinaba: 					R[0] = Q[0].front(), Q[0].pop();
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 			else
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				bool Go[] = {
4fd800b3a8 2011-02-23        kinaba: 					R[0]=='-' && Q[1].empty(),
4fd800b3a8 2011-02-23        kinaba: 					R[1]=='-' && Q[2].empty(),
4fd800b3a8 2011-02-23        kinaba: 					R[2]=='-' && Q[3].empty(),
4fd800b3a8 2011-02-23        kinaba: 					R[3]=='-' && Q[0].empty(),
4fd800b3a8 2011-02-23        kinaba: 				};
4fd800b3a8 2011-02-23        kinaba: 				for(int i=0; i<4; ++i)
4fd800b3a8 2011-02-23        kinaba: 					if( Go[i] && !Q[i].empty() )
4fd800b3a8 2011-02-23        kinaba: 						R[i] = Q[i].front(), Q[i].pop();
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			// clear ghost
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i<4; ++i)
4fd800b3a8 2011-02-23        kinaba: 				if( 'a'<=R[i] && R[i]<='z' )
4fd800b3a8 2011-02-23        kinaba: 					R[i] = '-';
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			// queue
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i<4; ++i)
4fd800b3a8 2011-02-23        kinaba: 				if( t < C[i].size() && C[i][t]!='-' )
4fd800b3a8 2011-02-23        kinaba: 					Q[i].push( C[i][t] );
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };