0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6f 6d 70 ..#include <comp
00d0: 6c 65 78 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c lex>..#include <
00e0: 71 75 65 75 65 3e 0d 0a 23 69 6e 63 6c 75 64 65 queue>..#include
00f0: 20 3c 73 74 61 63 6b 3e 0d 0a 23 69 6e 63 6c 75 <stack>..#inclu
0100: 64 65 20 3c 63 6d 61 74 68 3e 0d 0a 75 73 69 6e de <cmath>..usin
0110: 67 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b g namespace std;
0120: 0d 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c ..typedef long l
0130: 6f 6e 67 20 4c 4c 3b 0d 0a 0d 0a 69 6e 74 20 64 ong LL;....int d
0140: 79 5b 5d 20 3d 20 7b 2d 31 2c 31 2c 20 30 2c 30 y[] = {-1,1, 0,0
0150: 2c 2d 31 2c 2d 31 2c 20 31 2c 31 7d 3b 0d 0a 69 ,-1,-1, 1,1};..i
0160: 6e 74 20 64 78 5b 5d 20 3d 20 7b 20 30 2c 30 2c nt dx[] = { 0,0,
0170: 2d 31 2c 31 2c 2d 31 2c 20 31 2c 2d 31 2c 31 7d -1,1,-1, 1,-1,1}
0180: 3b 0d 0a 0d 0a 63 6c 61 73 73 20 4c 61 6e 64 41 ;....class LandA
0190: 6e 64 53 65 61 0d 0a 7b 0d 0a 70 75 62 6c 69 63 ndSea..{..public
01a0: 3a 0d 0a 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 :...vector<int>
01b0: 68 6f 77 4d 61 6e 79 49 73 6c 61 6e 64 73 28 76 howManyIslands(v
01c0: 65 63 74 6f 72 3c 73 74 72 69 6e 67 3e 20 73 65 ector<string> se
01d0: 61 4d 61 70 29 20 0d 0a 09 7b 0d 0a 09 09 63 6f aMap) ...{....co
01e0: 6e 73 74 20 69 6e 74 20 59 20 3d 20 73 65 61 4d nst int Y = seaM
01f0: 61 70 2e 73 69 7a 65 28 29 3b 0d 0a 09 09 63 6f ap.size();....co
0200: 6e 73 74 20 69 6e 74 20 58 20 3d 20 73 65 61 4d nst int X = seaM
0210: 61 70 5b 30 5d 2e 73 69 7a 65 28 29 3b 0d 0a 0d ap[0].size();...
0220: 0a 09 09 2f 2f 20 70 61 69 6e 74 0d 0a 09 09 76 ...// paint....v
0230: 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 69 6e ector< vector<in
0240: 74 3e 20 3e 20 69 64 4d 61 70 28 59 2c 20 76 65 t> > idMap(Y, ve
0250: 63 74 6f 72 3c 69 6e 74 3e 28 58 2c 20 2d 31 29 ctor<int>(X, -1)
0260: 29 3b 0d 0a 09 09 69 6e 74 20 6e 49 73 6c 61 6e );....int nIslan
0270: 64 20 3d 20 30 3b 0d 0a 09 09 66 6f 72 28 69 6e d = 0;....for(in
0280: 74 20 79 3d 30 3b 20 79 3c 59 3b 20 2b 2b 79 29 t y=0; y<Y; ++y)
0290: 0d 0a 09 09 66 6f 72 28 69 6e 74 20 78 3d 30 3b ....for(int x=0;
02a0: 20 78 3c 58 3b 20 2b 2b 78 29 0d 0a 09 09 09 69 x<X; ++x).....i
02b0: 66 28 20 73 65 61 4d 61 70 5b 79 5d 5b 78 5d 3d f( seaMap[y][x]=
02c0: 3d 27 78 27 20 26 26 20 69 64 4d 61 70 5b 79 5d ='x' && idMap[y]
02d0: 5b 78 5d 3d 3d 2d 31 20 29 0d 0a 09 09 09 7b 0d [x]==-1 ).....{.
02e0: 0a 09 09 09 09 69 6e 74 20 69 64 20 3d 20 28 69 .....int id = (i
02f0: 64 4d 61 70 5b 79 5d 5b 78 5d 20 3d 20 6e 49 73 dMap[y][x] = nIs
0300: 6c 61 6e 64 2b 2b 29 3b 0d 0a 09 09 09 09 73 74 land++);......st
0310: 61 63 6b 3c 20 70 61 69 72 3c 69 6e 74 2c 69 6e ack< pair<int,in
0320: 74 3e 20 3e 20 53 3b 0d 0a 09 09 09 09 53 2e 70 t> > S;......S.p
0330: 75 73 68 28 20 6d 61 6b 65 5f 70 61 69 72 28 79 ush( make_pair(y
0340: 2c 78 29 20 29 3b 0d 0a 09 09 09 09 77 68 69 6c ,x) );......whil
0350: 65 28 20 21 53 2e 65 6d 70 74 79 28 29 20 29 20 e( !S.empty() )
0360: 7b 0d 0a 09 09 09 09 09 70 61 69 72 3c 69 6e 74 {.......pair<int
0370: 2c 69 6e 74 3e 20 70 20 3d 20 53 2e 74 6f 70 28 ,int> p = S.top(
0380: 29 3b 20 20 53 2e 70 6f 70 28 29 3b 0d 0a 09 09 ); S.pop();....
0390: 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
03a0: 69 3c 38 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 i<8; ++i) {.....
03b0: 09 09 09 69 6e 74 20 79 79 20 3d 20 70 2e 66 69 ...int yy = p.fi
03c0: 72 73 74 20 2b 64 79 5b 69 5d 3b 0d 0a 09 09 09 rst +dy[i];.....
03d0: 09 09 09 69 6e 74 20 78 78 20 3d 20 70 2e 73 65 ...int xx = p.se
03e0: 63 6f 6e 64 2b 64 78 5b 69 5d 3b 0d 0a 09 09 09 cond+dx[i];.....
03f0: 09 09 09 69 66 28 20 30 3c 3d 79 79 20 26 26 20 ...if( 0<=yy &&
0400: 79 79 3c 59 20 26 26 20 30 3c 3d 78 78 20 26 26 yy<Y && 0<=xx &&
0410: 20 78 78 3c 58 20 29 0d 0a 09 09 09 09 09 09 09 xx<X ).........
0420: 69 66 28 20 73 65 61 4d 61 70 5b 79 79 5d 5b 78 if( seaMap[yy][x
0430: 78 5d 3d 3d 27 78 27 20 26 26 20 69 64 4d 61 70 x]=='x' && idMap
0440: 5b 79 79 5d 5b 78 78 5d 3d 3d 2d 31 20 29 0d 0a [yy][xx]==-1 )..
0450: 09 09 09 09 09 09 09 09 69 64 4d 61 70 5b 79 79 ........idMap[yy
0460: 5d 5b 78 78 5d 20 3d 20 69 64 2c 20 53 2e 70 75 ][xx] = id, S.pu
0470: 73 68 28 20 6d 61 6b 65 5f 70 61 69 72 28 79 79 sh( make_pair(yy
0480: 2c 78 78 29 20 29 3b 0d 0a 09 09 09 09 09 7d 0d ,xx) );.......}.
0490: 0a 09 09 09 09 7d 0d 0a 09 09 09 7d 0d 0a 0d 0a .....}.....}....
04a0: 09 09 2f 2f 20 49 20 69 73 20 63 6f 6e 74 61 69 ..// I is contai
04b0: 6e 65 64 20 62 79 20 4a 0d 0a 09 09 76 65 63 74 ned by J....vect
04c0: 6f 72 3c 69 6e 74 3e 20 72 65 66 65 72 65 64 28 or<int> refered(
04d0: 6e 49 73 6c 61 6e 64 29 3b 0d 0a 09 09 76 65 63 nIsland);....vec
04e0: 74 6f 72 3c 69 6e 74 3e 20 63 74 28 6e 49 73 6c tor<int> ct(nIsl
04f0: 61 6e 64 2c 20 2d 31 29 3b 0d 0a 0d 0a 09 09 73 and, -1);......s
0500: 65 74 3c 69 6e 74 3e 20 6f 75 74 65 72 5f 77 6f et<int> outer_wo
0510: 72 6c 64 3b 0d 0a 09 09 77 68 69 6c 65 28 20 6f rld;....while( o
0520: 75 74 65 72 5f 77 6f 72 6c 64 2e 73 69 7a 65 28 uter_world.size(
0530: 29 20 3c 20 6e 49 73 6c 61 6e 64 20 29 0d 0a 09 ) < nIsland )...
0540: 09 7b 0d 0a 09 09 09 73 65 74 3c 69 6e 74 3e 20 .{.....set<int>
0550: 6f 75 74 65 72 32 3b 0d 0a 09 09 09 66 6f 72 28 outer2;.....for(
0560: 69 6e 74 20 49 3d 30 3b 20 49 3c 6e 49 73 6c 61 int I=0; I<nIsla
0570: 6e 64 3b 20 2b 2b 49 29 0d 0a 09 09 09 09 69 66 nd; ++I)......if
0580: 28 20 21 6f 75 74 65 72 5f 77 6f 72 6c 64 2e 63 ( !outer_world.c
0590: 6f 75 6e 74 28 49 29 20 29 0d 0a 09 09 09 09 7b ount(I) )......{
05a0: 0d 0a 09 09 09 09 09 73 74 61 63 6b 3c 20 70 61 .......stack< pa
05b0: 69 72 3c 69 6e 74 2c 69 6e 74 3e 20 3e 20 53 3b ir<int,int> > S;
05c0: 0d 0a 09 09 09 09 09 73 65 74 3c 20 70 61 69 72 .......set< pair
05d0: 3c 69 6e 74 2c 69 6e 74 3e 20 3e 20 76 69 73 3b <int,int> > vis;
05e0: 0d 0a 09 09 09 09 09 66 6f 72 28 69 6e 74 20 79 .......for(int y
05f0: 3d 30 3b 20 79 3c 59 3b 20 2b 2b 79 29 0d 0a 09 =0; y<Y; ++y)...
0600: 09 09 09 09 09 66 6f 72 28 69 6e 74 20 78 3d 30 .....for(int x=0
0610: 3b 20 78 3c 58 3b 20 2b 2b 78 29 0d 0a 09 09 09 ; x<X; ++x).....
0620: 09 09 09 09 69 66 28 20 69 64 4d 61 70 5b 79 5d ....if( idMap[y]
0630: 5b 78 5d 20 3d 3d 20 49 20 29 0d 0a 09 09 09 09 [x] == I )......
0640: 09 09 09 09 53 2e 70 75 73 68 28 20 6d 61 6b 65 ....S.push( make
0650: 5f 70 61 69 72 28 79 2c 78 29 20 29 2c 20 76 69 _pair(y,x) ), vi
0660: 73 2e 69 6e 73 65 72 74 28 53 2e 74 6f 70 28 29 s.insert(S.top()
0670: 29 3b 0d 0a 0d 0a 09 09 09 09 09 69 6e 74 20 73 );.........int s
0680: 49 44 20 3d 20 2d 31 3b 0d 0a 09 09 09 09 09 77 ID = -1;.......w
0690: 68 69 6c 65 28 20 21 53 2e 65 6d 70 74 79 28 29 hile( !S.empty()
06a0: 20 29 20 7b 0d 0a 09 09 09 09 09 09 70 61 69 72 ) {........pair
06b0: 3c 69 6e 74 2c 69 6e 74 3e 20 70 20 3d 20 53 2e <int,int> p = S.
06c0: 74 6f 70 28 29 3b 20 20 53 2e 70 6f 70 28 29 3b top(); S.pop();
06d0: 0d 0a 09 09 09 09 09 09 66 6f 72 28 69 6e 74 20 ........for(int
06e0: 69 3d 30 3b 20 69 3c 34 3b 20 2b 2b 69 29 20 7b i=0; i<4; ++i) {
06f0: 0d 0a 09 09 09 09 09 09 09 69 6e 74 20 79 79 20 .........int yy
0700: 3d 20 70 2e 66 69 72 73 74 2b 64 79 5b 69 5d 3b = p.first+dy[i];
0710: 0d 0a 09 09 09 09 09 09 09 69 6e 74 20 78 78 20 .........int xx
0720: 3d 20 70 2e 73 65 63 6f 6e 64 2b 64 78 5b 69 5d = p.second+dx[i]
0730: 3b 0d 0a 09 09 09 09 09 09 09 69 66 28 20 21 28 ;.........if( !(
0740: 30 3c 3d 79 79 20 26 26 20 79 79 3c 59 20 26 26 0<=yy && yy<Y &&
0750: 20 30 3c 3d 78 78 20 26 26 20 78 78 3c 58 29 20 0<=xx && xx<X)
0760: 29 0d 0a 09 09 09 09 09 09 09 09 67 6f 74 6f 20 )..........goto
0770: 6e 6f 74 43 6f 6e 74 61 69 6e 65 64 3b 0d 0a 09 notContained;...
0780: 09 09 09 09 09 09 69 6e 74 20 73 73 49 44 20 3d ......int ssID =
0790: 20 69 64 4d 61 70 5b 79 79 5d 5b 78 78 5d 3b 0d idMap[yy][xx];.
07a0: 0a 09 09 09 09 09 09 09 69 66 28 20 6f 75 74 65 ........if( oute
07b0: 72 5f 77 6f 72 6c 64 2e 63 6f 75 6e 74 28 73 73 r_world.count(ss
07c0: 49 44 29 20 29 0d 0a 09 09 09 09 09 09 09 09 7b ID) )..........{
07d0: 73 49 44 3d 73 73 49 44 3b 20 67 6f 74 6f 20 6e sID=ssID; goto n
07e0: 6f 74 43 6f 6e 74 61 69 6e 65 64 3b 7d 0d 0a 0d otContained;}...
07f0: 0a 09 09 09 09 09 09 09 70 61 69 72 3c 69 6e 74 ........pair<int
0800: 2c 69 6e 74 3e 20 70 70 28 79 79 2c 78 78 29 3b ,int> pp(yy,xx);
0810: 0d 0a 09 09 09 09 09 09 09 69 66 28 20 21 76 69 .........if( !vi
0820: 73 2e 63 6f 75 6e 74 28 70 70 29 20 26 26 20 73 s.count(pp) && s
0830: 65 61 4d 61 70 5b 79 79 5d 5b 78 78 5d 3d 3d 27 eaMap[yy][xx]=='
0840: 2e 27 20 29 0d 0a 09 09 09 09 09 09 09 09 53 2e .' )..........S.
0850: 70 75 73 68 28 70 70 29 2c 20 76 69 73 2e 69 6e push(pp), vis.in
0860: 73 65 72 74 28 53 2e 74 6f 70 28 29 29 3b 0d 0a sert(S.top());..
0870: 09 09 09 09 09 09 7d 0d 0a 09 09 09 09 09 7d 0d ......}.......}.
0880: 0a 09 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0d ......continue;.
0890: 0a 09 09 09 09 6e 6f 74 43 6f 6e 74 61 69 6e 65 .....notContaine
08a0: 64 3a 0d 0a 09 09 09 09 09 6f 75 74 65 72 32 2e d:.......outer2.
08b0: 69 6e 73 65 72 74 28 49 29 3b 0d 0a 09 09 09 09 insert(I);......
08c0: 09 69 66 28 73 49 44 20 21 3d 20 2d 31 29 20 7b .if(sID != -1) {
08d0: 0d 0a 09 09 09 09 09 09 63 74 5b 49 5d 20 3d 20 ........ct[I] =
08e0: 73 49 44 3b 0d 0a 09 09 09 09 09 09 72 65 66 65 sID;........refe
08f0: 72 65 64 5b 73 49 44 5d 2b 2b 3b 0d 0a 09 09 09 red[sID]++;.....
0900: 09 09 7d 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 6f ..}......}.....o
0910: 75 74 65 72 5f 77 6f 72 6c 64 2e 69 6e 73 65 72 uter_world.inser
0920: 74 28 6f 75 74 65 72 32 2e 62 65 67 69 6e 28 29 t(outer2.begin()
0930: 2c 20 6f 75 74 65 72 32 2e 65 6e 64 28 29 29 3b , outer2.end());
0940: 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 2f 2f 20 74 6f ....}......// to
0950: 70 6f 6c 6f 67 69 63 61 6c 20 73 6f 72 74 0d 0a pological sort..
0960: 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 6c 65 ..vector<int> le
0970: 76 65 6c 28 6e 49 73 6c 61 6e 64 2c 20 2d 31 29 vel(nIsland, -1)
0980: 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 4c 3d 30 ;....for(int L=0
0990: 3b 3b 2b 2b 4c 29 0d 0a 09 09 7b 0d 0a 09 09 09 ;;++L)....{.....
09a0: 76 65 63 74 6f 72 3c 69 6e 74 3e 20 76 69 63 74 vector<int> vict
09b0: 69 6d 3b 0d 0a 0d 0a 09 09 09 66 6f 72 28 69 6e im;.......for(in
09c0: 74 20 49 3d 30 3b 20 49 3c 6e 49 73 6c 61 6e 64 t I=0; I<nIsland
09d0: 3b 20 2b 2b 49 29 0d 0a 09 09 09 09 69 66 28 20 ; ++I)......if(
09e0: 6c 65 76 65 6c 5b 49 5d 20 3d 3d 20 2d 31 20 26 level[I] == -1 &
09f0: 26 20 72 65 66 65 72 65 64 5b 49 5d 20 3d 3d 20 & refered[I] ==
0a00: 30 20 29 0d 0a 09 09 09 09 09 6c 65 76 65 6c 5b 0 ).......level[
0a10: 49 5d 20 3d 20 4c 2c 20 76 69 63 74 69 6d 2e 70 I] = L, victim.p
0a20: 75 73 68 5f 62 61 63 6b 28 49 29 3b 0d 0a 0d 0a ush_back(I);....
0a30: 09 09 09 69 66 28 20 76 69 63 74 69 6d 2e 73 69 ...if( victim.si
0a40: 7a 65 28 29 20 3d 3d 20 30 20 29 0d 0a 09 09 09 ze() == 0 ).....
0a50: 09 62 72 65 61 6b 3b 0d 0a 0d 0a 09 09 09 66 6f .break;.......fo
0a60: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 76 69 63 r(int i=0; i<vic
0a70: 74 69 6d 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 tim.size(); ++i)
0a80: 0d 0a 09 09 09 7b 0d 0a 09 09 09 09 69 6e 74 20 .....{......int
0a90: 4a 20 3d 20 63 74 5b 76 69 63 74 69 6d 5b 69 5d J = ct[victim[i]
0aa0: 5d 3b 0d 0a 09 09 09 09 69 66 28 20 4a 20 21 3d ];......if( J !=
0ab0: 20 2d 31 20 29 0d 0a 09 09 09 09 09 72 65 66 65 -1 ).......refe
0ac0: 72 65 64 5b 4a 5d 2d 2d 3b 0d 0a 09 09 09 7d 0d red[J]--;.....}.
0ad0: 0a 09 09 7d 0d 0a 0d 0a 09 09 76 65 63 74 6f 72 ...}......vector
0ae0: 3c 69 6e 74 3e 20 61 6e 73 3b 0d 0a 09 09 66 6f <int> ans;....fo
0af0: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6c 65 76 r(int i=0; i<lev
0b00: 65 6c 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 20 el.size(); ++i)
0b10: 7b 0d 0a 09 09 09 69 66 28 20 6c 65 76 65 6c 5b {.....if( level[
0b20: 69 5d 2b 31 20 3e 20 61 6e 73 2e 73 69 7a 65 28 i]+1 > ans.size(
0b30: 29 20 29 0d 0a 09 09 09 09 61 6e 73 2e 72 65 73 ) )......ans.res
0b40: 69 7a 65 28 20 6c 65 76 65 6c 5b 69 5d 2b 31 20 ize( level[i]+1
0b50: 29 3b 0d 0a 09 09 09 61 6e 73 5b 6c 65 76 65 6c );.....ans[level
0b60: 5b 69 5d 5d 2b 2b 3b 0d 0a 09 09 7d 0d 0a 09 09 [i]]++;....}....
0b70: 72 65 74 75 72 6e 20 61 6e 73 3b 0d 0a 09 7d 0d return ans;...}.
0b80: 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 ...// BEGIN CUT
0b90: 48 45 52 45 0d 0a 09 70 75 62 6c 69 63 3a 0d 0a HERE...public:..
0ba0: 09 76 6f 69 64 20 72 75 6e 5f 74 65 73 74 28 69 .void run_test(i
0bb0: 6e 74 20 43 61 73 65 29 20 7b 20 69 66 20 28 28 nt Case) { if ((
0bc0: 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 Case == -1) || (
0bd0: 43 61 73 65 20 3d 3d 20 30 29 29 20 74 65 73 74 Case == 0)) test
0be0: 5f 63 61 73 65 5f 30 28 29 3b 20 69 66 20 28 28 _case_0(); if ((
0bf0: 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 Case == -1) || (
0c00: 43 61 73 65 20 3d 3d 20 31 29 29 20 74 65 73 74 Case == 1)) test
0c10: 5f 63 61 73 65 5f 31 28 29 3b 20 69 66 20 28 28 _case_1(); if ((
0c20: 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 Case == -1) || (
0c30: 43 61 73 65 20 3d 3d 20 32 29 29 20 74 65 73 74 Case == 2)) test
0c40: 5f 63 61 73 65 5f 32 28 29 3b 20 69 66 20 28 28 _case_2(); if ((
0c50: 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 Case == -1) || (
0c60: 43 61 73 65 20 3d 3d 20 33 29 29 20 74 65 73 74 Case == 3)) test
0c70: 5f 63 61 73 65 5f 33 28 29 3b 20 69 66 20 28 28 _case_3(); if ((
0c80: 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 Case == -1) || (
0c90: 43 61 73 65 20 3d 3d 20 34 29 29 20 74 65 73 74 Case == 4)) test
0ca0: 5f 63 61 73 65 5f 34 28 29 3b 20 7d 0d 0a 09 70 _case_4(); }...p
0cb0: 72 69 76 61 74 65 3a 0d 0a 09 74 65 6d 70 6c 61 rivate:...templa
0cc0: 74 65 20 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 te <typename T>
0cd0: 73 74 72 69 6e 67 20 70 72 69 6e 74 5f 61 72 72 string print_arr
0ce0: 61 79 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c ay(const vector<
0cf0: 54 3e 20 26 56 29 20 7b 20 6f 73 74 72 69 6e 67 T> &V) { ostring
0d00: 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c 3c stream os; os <<
0d10: 20 22 7b 20 22 3b 20 66 6f 72 20 28 74 79 70 65 "{ "; for (type
0d20: 6e 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a name vector<T>::
0d30: 63 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 69 const_iterator i
0d40: 74 65 72 20 3d 20 56 2e 62 65 67 69 6e 28 29 3b ter = V.begin();
0d50: 20 69 74 65 72 20 21 3d 20 56 2e 65 6e 64 28 29 iter != V.end()
0d60: 3b 20 2b 2b 69 74 65 72 29 20 6f 73 20 3c 3c 20 ; ++iter) os <<
0d70: 27 5c 22 27 20 3c 3c 20 2a 69 74 65 72 20 3c 3c '\"' << *iter <<
0d80: 20 22 5c 22 2c 22 3b 20 6f 73 20 3c 3c 20 22 20 "\","; os << "
0d90: 7d 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 74 }"; return os.st
0da0: 72 28 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 76 65 r(); }...void ve
0db0: 72 69 66 79 5f 63 61 73 65 28 69 6e 74 20 43 61 rify_case(int Ca
0dc0: 73 65 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 se, const vector
0dd0: 20 3c 69 6e 74 3e 20 26 45 78 70 65 63 74 65 64 <int> &Expected
0de0: 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 20 3c , const vector <
0df0: 69 6e 74 3e 20 26 52 65 63 65 69 76 65 64 29 20 int> &Received)
0e00: 7b 20 63 65 72 72 20 3c 3c 20 22 54 65 73 74 20 { cerr << "Test
0e10: 43 61 73 65 20 23 22 20 3c 3c 20 43 61 73 65 20 Case #" << Case
0e20: 3c 3c 20 22 2e 2e 2e 22 3b 20 69 66 20 28 45 78 << "..."; if (Ex
0e30: 70 65 63 74 65 64 20 3d 3d 20 52 65 63 65 69 76 pected == Receiv
0e40: 65 64 29 20 63 65 72 72 20 3c 3c 20 22 50 41 53 ed) cerr << "PAS
0e50: 53 45 44 22 20 3c 3c 20 65 6e 64 6c 3b 20 65 6c SED" << endl; el
0e60: 73 65 20 7b 20 63 65 72 72 20 3c 3c 20 22 46 41 se { cerr << "FA
0e70: 49 4c 45 44 22 20 3c 3c 20 65 6e 64 6c 3b 20 63 ILED" << endl; c
0e80: 65 72 72 20 3c 3c 20 22 5c 74 45 78 70 65 63 74 err << "\tExpect
0e90: 65 64 3a 20 22 20 3c 3c 20 70 72 69 6e 74 5f 61 ed: " << print_a
0ea0: 72 72 61 79 28 45 78 70 65 63 74 65 64 29 20 3c rray(Expected) <
0eb0: 3c 20 65 6e 64 6c 3b 20 63 65 72 72 20 3c 3c 20 < endl; cerr <<
0ec0: 22 5c 74 52 65 63 65 69 76 65 64 3a 20 22 20 3c "\tReceived: " <
0ed0: 3c 20 70 72 69 6e 74 5f 61 72 72 61 79 28 52 65 < print_array(Re
0ee0: 63 65 69 76 65 64 29 20 3c 3c 20 65 6e 64 6c 3b ceived) << endl;
0ef0: 20 7d 20 7d 0d 0a 09 76 6f 69 64 20 74 65 73 74 } }...void test
0f00: 5f 63 61 73 65 5f 30 28 29 20 7b 20 73 74 72 69 _case_0() { stri
0f10: 6e 67 20 41 72 72 30 5b 5d 20 3d 20 7b 22 78 22 ng Arr0[] = {"x"
0f20: 7d 3b 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e }; vector <strin
0f30: 67 3e 20 41 72 67 30 28 41 72 72 30 2c 20 41 72 g> Arg0(Arr0, Ar
0f40: 72 30 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 r0 + (sizeof(Arr
0f50: 30 29 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 30 0) / sizeof(Arr0
0f60: 5b 30 5d 29 29 29 3b 20 69 6e 74 20 41 72 72 31 [0]))); int Arr1
0f70: 5b 5d 20 3d 20 7b 31 20 7d 3b 20 76 65 63 74 6f [] = {1 }; vecto
0f80: 72 20 3c 69 6e 74 3e 20 41 72 67 31 28 41 72 72 r <int> Arg1(Arr
0f90: 31 2c 20 41 72 72 31 20 2b 20 28 73 69 7a 65 6f 1, Arr1 + (sizeo
0fa0: 66 28 41 72 72 31 29 20 2f 20 73 69 7a 65 6f 66 f(Arr1) / sizeof
0fb0: 28 41 72 72 31 5b 30 5d 29 29 29 3b 20 76 65 72 (Arr1[0]))); ver
0fc0: 69 66 79 5f 63 61 73 65 28 30 2c 20 41 72 67 31 ify_case(0, Arg1
0fd0: 2c 20 68 6f 77 4d 61 6e 79 49 73 6c 61 6e 64 73 , howManyIslands
0fe0: 28 41 72 67 30 29 29 3b 20 7d 0d 0a 09 76 6f 69 (Arg0)); }...voi
0ff0: 64 20 74 65 73 74 5f 63 61 73 65 5f 31 28 29 20 d test_case_1()
1000: 7b 20 73 74 72 69 6e 67 20 41 72 72 30 5b 5d 20 { string Arr0[]
1010: 3d 20 7b 0d 0a 22 78 78 78 78 78 22 2c 0d 0a 22 = {.."xxxxx",.."
1020: 78 2e 2e 2e 78 22 2c 0d 0a 22 78 2e 78 2e 78 22 x...x",.."x.x.x"
1030: 2c 0d 0a 22 78 2e 2e 2e 78 22 2c 0d 0a 22 78 78 ,.."x...x",.."xx
1040: 78 78 78 22 0d 0a 7d 3b 20 76 65 63 74 6f 72 20 xxx"..}; vector
1050: 3c 73 74 72 69 6e 67 3e 20 41 72 67 30 28 41 72 <string> Arg0(Ar
1060: 72 30 2c 20 41 72 72 30 20 2b 20 28 73 69 7a 65 r0, Arr0 + (size
1070: 6f 66 28 41 72 72 30 29 20 2f 20 73 69 7a 65 6f of(Arr0) / sizeo
1080: 66 28 41 72 72 30 5b 30 5d 29 29 29 3b 20 69 6e f(Arr0[0]))); in
1090: 74 20 41 72 72 31 5b 5d 20 3d 20 7b 31 2c 20 31 t Arr1[] = {1, 1
10a0: 20 7d 3b 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e }; vector <int>
10b0: 20 41 72 67 31 28 41 72 72 31 2c 20 41 72 72 31 Arg1(Arr1, Arr1
10c0: 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 31 29 + (sizeof(Arr1)
10d0: 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 31 5b 30 / sizeof(Arr1[0
10e0: 5d 29 29 29 3b 20 76 65 72 69 66 79 5f 63 61 73 ]))); verify_cas
10f0: 65 28 31 2c 20 41 72 67 31 2c 20 68 6f 77 4d 61 e(1, Arg1, howMa
1100: 6e 79 49 73 6c 61 6e 64 73 28 41 72 67 30 29 29 nyIslands(Arg0))
1110: 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 65 73 74 5f ; }...void test_
1120: 63 61 73 65 5f 32 28 29 20 7b 20 73 74 72 69 6e case_2() { strin
1130: 67 20 41 72 72 30 5b 5d 20 3d 20 7b 0d 0a 22 78 g Arr0[] = {.."x
1140: 78 78 78 78 22 2c 0d 0a 22 78 2e 2e 2e 78 22 2c xxxx",.."x...x",
1150: 0d 0a 22 78 2e 78 2e 78 22 2c 0d 0a 22 78 2e 2e .."x.x.x",.."x..
1160: 2e 78 22 2c 0d 0a 22 78 78 78 78 78 22 2c 0d 0a .x",.."xxxxx",..
1170: 22 78 78 78 78 78 22 2c 0d 0a 22 78 2e 2e 2e 78 "xxxxx",.."x...x
1180: 22 2c 0d 0a 22 78 2e 78 2e 78 22 2c 0d 0a 22 78 ",.."x.x.x",.."x
1190: 2e 2e 2e 78 22 2c 0d 0a 22 78 78 78 78 78 22 0d ...x",.."xxxxx".
11a0: 0a 7d 3b 20 76 65 63 74 6f 72 20 3c 73 74 72 69 .}; vector <stri
11b0: 6e 67 3e 20 41 72 67 30 28 41 72 72 30 2c 20 41 ng> Arg0(Arr0, A
11c0: 72 72 30 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 rr0 + (sizeof(Ar
11d0: 72 30 29 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 r0) / sizeof(Arr
11e0: 30 5b 30 5d 29 29 29 3b 20 69 6e 74 20 41 72 72 0[0]))); int Arr
11f0: 31 5b 5d 20 3d 20 7b 32 2c 20 31 20 7d 3b 20 76 1[] = {2, 1 }; v
1200: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 41 72 67 31 ector <int> Arg1
1210: 28 41 72 72 31 2c 20 41 72 72 31 20 2b 20 28 73 (Arr1, Arr1 + (s
1220: 69 7a 65 6f 66 28 41 72 72 31 29 20 2f 20 73 69 izeof(Arr1) / si
1230: 7a 65 6f 66 28 41 72 72 31 5b 30 5d 29 29 29 3b zeof(Arr1[0])));
1240: 20 76 65 72 69 66 79 5f 63 61 73 65 28 32 2c 20 verify_case(2,
1250: 41 72 67 31 2c 20 68 6f 77 4d 61 6e 79 49 73 6c Arg1, howManyIsl
1260: 61 6e 64 73 28 41 72 67 30 29 29 3b 20 7d 0d 0a ands(Arg0)); }..
1270: 09 76 6f 69 64 20 74 65 73 74 5f 63 61 73 65 5f .void test_case_
1280: 33 28 29 20 7b 20 73 74 72 69 6e 67 20 41 72 72 3() { string Arr
1290: 30 5b 5d 20 3d 20 7b 0d 0a 22 2e 2e 22 2c 0d 0a 0[] = {.."..",..
12a0: 22 2e 2e 22 0d 0a 7d 3b 20 76 65 63 74 6f 72 20 ".."..}; vector
12b0: 3c 73 74 72 69 6e 67 3e 20 41 72 67 30 28 41 72 <string> Arg0(Ar
12c0: 72 30 2c 20 41 72 72 30 20 2b 20 28 73 69 7a 65 r0, Arr0 + (size
12d0: 6f 66 28 41 72 72 30 29 20 2f 20 73 69 7a 65 6f of(Arr0) / sizeo
12e0: 66 28 41 72 72 30 5b 30 5d 29 29 29 3b 20 76 65 f(Arr0[0]))); ve
12f0: 63 74 6f 72 20 3c 69 6e 74 3e 20 41 72 67 31 3b ctor <int> Arg1;
1300: 20 76 65 72 69 66 79 5f 63 61 73 65 28 33 2c 20 verify_case(3,
1310: 41 72 67 31 2c 20 68 6f 77 4d 61 6e 79 49 73 6c Arg1, howManyIsl
1320: 61 6e 64 73 28 41 72 67 30 29 29 3b 20 7d 0d 0a ands(Arg0)); }..
1330: 09 76 6f 69 64 20 74 65 73 74 5f 63 61 73 65 5f .void test_case_
1340: 34 28 29 20 7b 20 73 74 72 69 6e 67 20 41 72 72 4() { string Arr
1350: 30 5b 5d 20 3d 20 7b 0d 0a 22 2e 2e 2e 2e 2e 2e 0[] = {.."......
1360: 2e 2e 2e 2e 2e 2e 22 2c 0d 0a 22 2e 2e 2e 2e 2e ......",..".....
1370: 2e 2e 78 78 78 78 2e 22 2c 0d 0a 22 2e 2e 78 78 ..xxxx.",.."..xx
1380: 78 2e 78 2e 2e 2e 78 2e 22 2c 0d 0a 22 2e 2e 78 x.x...x.",.."..x
1390: 2e 2e 78 2e 2e 78 2e 78 2e 22 2c 0d 0a 22 2e 2e ..x..x.x.",.."..
13a0: 78 2e 78 2e 78 2e 2e 2e 78 2e 22 2c 0d 0a 22 2e x.x.x...x.",..".
13b0: 2e 78 78 2e 2e 2e 78 78 78 2e 2e 22 0d 0a 7d 3b .xx...xxx.."..};
13c0: 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e vector <string>
13d0: 20 41 72 67 30 28 41 72 72 30 2c 20 41 72 72 30 Arg0(Arr0, Arr0
13e0: 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 30 29 + (sizeof(Arr0)
13f0: 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 30 5b 30 / sizeof(Arr0[0
1400: 5d 29 29 29 3b 20 69 6e 74 20 41 72 72 31 5b 5d ]))); int Arr1[]
1410: 20 3d 20 7b 31 2c 20 31 20 7d 3b 20 76 65 63 74 = {1, 1 }; vect
1420: 6f 72 20 3c 69 6e 74 3e 20 41 72 67 31 28 41 72 or <int> Arg1(Ar
1430: 72 31 2c 20 41 72 72 31 20 2b 20 28 73 69 7a 65 r1, Arr1 + (size
1440: 6f 66 28 41 72 72 31 29 20 2f 20 73 69 7a 65 6f of(Arr1) / sizeo
1450: 66 28 41 72 72 31 5b 30 5d 29 29 29 3b 20 76 65 f(Arr1[0]))); ve
1460: 72 69 66 79 5f 63 61 73 65 28 34 2c 20 41 72 67 rify_case(4, Arg
1470: 31 2c 20 68 6f 77 4d 61 6e 79 49 73 6c 61 6e 64 1, howManyIsland
1480: 73 28 41 72 67 30 29 29 3b 20 7d 0d 0a 0d 0a 2f s(Arg0)); }..../
1490: 2f 20 45 4e 44 20 43 55 54 20 48 45 52 45 0d 0a / END CUT HERE..
14a0: 7d 3b 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 };..// BEGIN CUT
14b0: 20 48 45 52 45 20 0d 0a 69 6e 74 20 6d 61 69 6e HERE ..int main
14c0: 28 29 20 7b 20 4c 61 6e 64 41 6e 64 53 65 61 28 () { LandAndSea(
14d0: 29 2e 72 75 6e 5f 74 65 73 74 28 2d 31 29 3b 20 ).run_test(-1);
14e0: 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 20 48 45 }..// END CUT HE
14f0: 52 45 0d 0a RE..