Artifact 561b82c7ab9e8ca630227cd0a012680494476943:
0000: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0010: 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 71 75 65 75 >.#include <queu
0020: 65 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 e>.#include <alg
0030: 6f 72 69 74 68 6d 3e 0a 75 73 69 6e 67 20 6e 61 orithm>.using na
0040: 6d 65 73 70 61 63 65 20 73 74 64 3b 0a 0a 73 74 mespace std;..st
0050: 72 75 63 74 20 52 6f 75 6e 64 61 62 6f 75 74 0a ruct Roundabout.
0060: 7b 0a 09 69 6e 74 20 63 6c 65 61 72 55 70 54 69 {..int clearUpTi
0070: 6d 65 28 73 74 72 69 6e 67 20 6e 6f 72 74 68 2c me(string north,
0080: 20 73 74 72 69 6e 67 20 65 61 73 74 2c 20 73 74 string east, st
0090: 72 69 6e 67 20 73 6f 75 74 68 2c 20 73 74 72 69 ring south, stri
00a0: 6e 67 20 77 65 73 74 29 0a 09 7b 0a 09 09 63 68 ng west)..{...ch
00b0: 61 72 20 20 20 20 20 20 20 20 4d 5b 34 5d 20 3d ar M[4] =
00c0: 20 7b 27 4e 27 2c 20 27 45 27 2c 20 27 53 27 2c {'N', 'E', 'S',
00d0: 20 27 57 27 7d 3b 0a 09 09 73 74 72 69 6e 67 20 'W'};...string
00e0: 20 20 20 20 20 43 5b 34 5d 20 3d 20 7b 6e 6f 72 C[4] = {nor
00f0: 74 68 2c 20 65 61 73 74 2c 20 73 6f 75 74 68 2c th, east, south,
0100: 20 77 65 73 74 7d 3b 0a 09 09 63 68 61 72 20 20 west};...char
0110: 20 20 20 20 20 20 52 5b 34 5d 20 3d 20 7b 27 2d R[4] = {'-
0120: 27 2c 20 27 2d 27 2c 20 27 2d 27 2c 20 27 2d 27 ', '-', '-', '-'
0130: 7d 3b 0a 09 09 71 75 65 75 65 3c 63 68 61 72 3e };...queue<char>
0140: 20 51 5b 34 5d 3b 0a 0a 09 09 69 6e 74 20 4e 20 Q[4];....int N
0150: 3d 20 30 3b 0a 09 09 66 6f 72 28 69 6e 74 20 69 = 0;...for(int i
0160: 3d 30 3b 20 69 3c 34 3b 20 2b 2b 69 29 0a 09 09 =0; i<4; ++i)...
0170: 09 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c .for(int j=0; j<
0180: 43 5b 69 5d 2e 73 69 7a 65 28 29 3b 20 2b 2b 6a C[i].size(); ++j
0190: 29 0a 09 09 09 09 69 66 28 20 43 5b 69 5d 5b 6a ).....if( C[i][j
01a0: 5d 20 21 3d 20 27 2d 27 20 29 0a 09 09 09 09 09 ] != '-' )......
01b0: 2b 2b 4e 3b 0a 0a 09 09 69 6e 74 20 74 20 3d 20 ++N;....int t =
01c0: 30 3b 0a 09 09 66 6f 72 28 20 3b 3b 20 2b 2b 74 0;...for( ;; ++t
01d0: 20 29 0a 09 09 7b 0a 09 09 09 2f 2f 20 6c 65 61 )...{....// lea
01e0: 76 65 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 3d ve....for(int i=
01f0: 30 3b 20 69 3c 34 3b 20 2b 2b 69 29 0a 09 09 09 0; i<4; ++i)....
0200: 09 69 66 28 20 52 5b 69 5d 20 3d 3d 20 4d 5b 69 .if( R[i] == M[i
0210: 5d 20 29 0a 09 09 09 09 09 52 5b 69 5d 20 3d 20 ] )......R[i] =
0220: 4d 5b 69 5d 2d 27 41 27 2b 27 61 27 2c 20 2d 2d M[i]-'A'+'a', --
0230: 4e 3b 20 2f 2f 20 70 75 74 20 67 68 6f 73 74 73 N; // put ghosts
0240: 0a 09 09 09 69 66 28 20 21 4e 20 29 0a 09 09 09 ....if( !N )....
0250: 09 72 65 74 75 72 6e 20 74 3b 0a 0a 09 09 09 2f .return t;...../
0260: 2f 20 72 6f 74 61 74 65 0a 09 09 09 72 6f 74 61 / rotate....rota
0270: 74 65 28 20 52 2b 30 2c 20 52 2b 31 2c 20 52 2b te( R+0, R+1, R+
0280: 34 20 29 3b 0a 0a 09 09 09 2f 2f 20 65 6e 74 65 4 );.....// ente
0290: 72 0a 09 09 09 69 66 28 20 21 51 5b 30 5d 2e 65 r....if( !Q[0].e
02a0: 6d 70 74 79 28 29 20 26 26 20 21 51 5b 31 5d 2e mpty() && !Q[1].
02b0: 65 6d 70 74 79 28 29 20 26 26 20 21 51 5b 32 5d empty() && !Q[2]
02c0: 2e 65 6d 70 74 79 28 29 20 26 26 20 21 51 5b 33 .empty() && !Q[3
02d0: 5d 2e 65 6d 70 74 79 28 29 20 29 0a 09 09 09 7b ].empty() )....{
02e0: 0a 09 09 09 09 69 66 28 20 52 5b 30 5d 3d 3d 27 .....if( R[0]=='
02f0: 2d 27 20 29 0a 09 09 09 09 09 52 5b 30 5d 20 3d -' )......R[0] =
0300: 20 51 5b 30 5d 2e 66 72 6f 6e 74 28 29 2c 20 51 Q[0].front(), Q
0310: 5b 30 5d 2e 70 6f 70 28 29 3b 0a 09 09 09 7d 0a [0].pop();....}.
0320: 09 09 09 65 6c 73 65 0a 09 09 09 7b 0a 09 09 09 ...else....{....
0330: 09 62 6f 6f 6c 20 47 6f 5b 5d 20 3d 20 7b 0a 09 .bool Go[] = {..
0340: 09 09 09 09 52 5b 30 5d 3d 3d 27 2d 27 20 26 26 ....R[0]=='-' &&
0350: 20 51 5b 31 5d 2e 65 6d 70 74 79 28 29 2c 0a 09 Q[1].empty(),..
0360: 09 09 09 09 52 5b 31 5d 3d 3d 27 2d 27 20 26 26 ....R[1]=='-' &&
0370: 20 51 5b 32 5d 2e 65 6d 70 74 79 28 29 2c 0a 09 Q[2].empty(),..
0380: 09 09 09 09 52 5b 32 5d 3d 3d 27 2d 27 20 26 26 ....R[2]=='-' &&
0390: 20 51 5b 33 5d 2e 65 6d 70 74 79 28 29 2c 0a 09 Q[3].empty(),..
03a0: 09 09 09 09 52 5b 33 5d 3d 3d 27 2d 27 20 26 26 ....R[3]=='-' &&
03b0: 20 51 5b 30 5d 2e 65 6d 70 74 79 28 29 2c 0a 09 Q[0].empty(),..
03c0: 09 09 09 7d 3b 0a 09 09 09 09 66 6f 72 28 69 6e ...};.....for(in
03d0: 74 20 69 3d 30 3b 20 69 3c 34 3b 20 2b 2b 69 29 t i=0; i<4; ++i)
03e0: 0a 09 09 09 09 09 69 66 28 20 47 6f 5b 69 5d 20 ......if( Go[i]
03f0: 26 26 20 21 51 5b 69 5d 2e 65 6d 70 74 79 28 29 && !Q[i].empty()
0400: 20 29 0a 09 09 09 09 09 09 52 5b 69 5d 20 3d 20 ).......R[i] =
0410: 51 5b 69 5d 2e 66 72 6f 6e 74 28 29 2c 20 51 5b Q[i].front(), Q[
0420: 69 5d 2e 70 6f 70 28 29 3b 0a 09 09 09 7d 0a 0a i].pop();....}..
0430: 09 09 09 2f 2f 20 63 6c 65 61 72 20 67 68 6f 73 ...// clear ghos
0440: 74 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 t....for(int i=0
0450: 3b 20 69 3c 34 3b 20 2b 2b 69 29 0a 09 09 09 09 ; i<4; ++i).....
0460: 69 66 28 20 27 61 27 3c 3d 52 5b 69 5d 20 26 26 if( 'a'<=R[i] &&
0470: 20 52 5b 69 5d 3c 3d 27 7a 27 20 29 0a 09 09 09 R[i]<='z' )....
0480: 09 09 52 5b 69 5d 20 3d 20 27 2d 27 3b 0a 0a 09 ..R[i] = '-';...
0490: 09 09 2f 2f 20 71 75 65 75 65 0a 09 09 09 66 6f ..// queue....fo
04a0: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 34 3b 20 r(int i=0; i<4;
04b0: 2b 2b 69 29 0a 09 09 09 09 69 66 28 20 74 20 3c ++i).....if( t <
04c0: 20 43 5b 69 5d 2e 73 69 7a 65 28 29 20 26 26 20 C[i].size() &&
04d0: 43 5b 69 5d 5b 74 5d 21 3d 27 2d 27 20 29 0a 09 C[i][t]!='-' )..
04e0: 09 09 09 09 51 5b 69 5d 2e 70 75 73 68 28 20 43 ....Q[i].push( C
04f0: 5b 69 5d 5b 74 5d 20 29 3b 0a 09 09 7d 0a 09 7d [i][t] );...}..}
0500: 0a 7d 3b 0a .};.