package Ġle et code . mock Ċ Ċ import Ġorg . junit . Assert .* Ċ import Ġorg . junit . Test Ċ import Ġjava . lang . StringBuilder Ċ Ċ class ĠMock Inter view 1 6 Test Ġ{ ĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġ` test Ġcase Ġ 1 `() Ġ{ ĊĊĠĠĠ Ġ} Ċ } Ċ Ċ object ĠMock Inter view 1 6 Ġ{ ĊĠĠĠ Ġfun Ġgroup Strings ( strings : ĠArray < String >): ĠList < List < String >> Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġstrings . groupBy Ġ{ Ġnormalize ( it ) Ġ}. values . toList () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġnormalize ( s : ĠString ): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnormalized Ġ= ĠStringBuilder () ĊĠĠĠĠĠĠĠ Ġif Ġ( s . isEmpty ()) Ġreturn Ġs ĊĠĠĠĠĠĠĠ Ġval Ġdiff Ġ= Ġ' z ' Ġ- Ġs [ 0 ] ĊĠĠĠĠĠĠĠ Ġs . forEach Ġ{ Ġc Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew C Ġ= Ġ' a ' Ġ+ Ġ((( c Ġ- Ġ' a ') Ġ+ Ġdiff ) Ġ% Ġ 2 6 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnormalized . append ( new C ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġnormalized . toString () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġval Ġdi Ġ= ĠlistOf ( 1 , Ġ- 1 , Ġ 0 , Ġ 0 ) ĊĠĠĠ Ġprivate Ġval Ġdj Ġ= ĠlistOf ( 0 , Ġ 0 , Ġ 1 , Ġ- 1 ) ĊĊĠĠĠ Ġfun Ġnum Is lands ( grid : ĠArray < CharArray >): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġn Ġ= Ġgrid . size ĊĠĠĠĠĠĠĠ Ġval Ġm Ġ= Ġgrid . size ĊĠĠĠĠĠĠĠ Ġval Ġvisited Ġ= ĠHashSet < Point >() ĊĊĠĠĠĠĠĠĠ Ġvar Ġcnt Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 Ġuntil Ġm ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp Ġ= ĠPoint ( i , Ġj ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( grid [ i ][ j ] Ġ== Ġ' 1 ' Ġ&& Ġ! visited . contains ( p )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcnt ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdfs ( p , Ġgrid , Ġvisited ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġcnt ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġdfs ( p : ĠPoint , Ġgrid : ĠArray < CharArray >, Ġvisited : ĠHashSet < Point >) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( grid [ p . i ][ p . j ] Ġ== Ġ' 0 ') Ġreturn ĊĠĠĠĠĠĠĠ Ġvisited . add ( p ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( d Ġin Ġdi . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Point Ġ= ĠPoint ( p . i Ġ+ Ġdi [ d ], Ġp . j Ġ+ Ġdj [ d ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( new Point . isValid ( grid . size , Ġgrid . first (). size ) Ġ&& Ġ! visited . contains ( new Point )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdfs ( new Point , Ġgrid , Ġvisited ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġdata Ġclass ĠPoint ( val Ġi : ĠInt , Ġval Ġj : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfun ĠisValid ( n : ĠInt , Ġm : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġi Ġin Ġ 0 Ġuntil Ġn Ġ&& Ġj Ġin Ġ 0 Ġuntil Ġm ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/// Ġproblem Ġ 4 ĊĊĠĠĠ Ġ// Ġo Ġ( Ġk Ġ* Ġlon Ġ( Ġn * m Ġ) Ġ) ĊĠĠĠ Ġfun Ġnum Is lands 2 ( m : ĠInt , Ġn : ĠInt , Ġpositions : ĠArray < IntArray >): ĠList < Int > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġunion Find Ġ= ĠUnion Find () ĊĠĠĠĠĠĠĠ Ġval Ġgrid Ġ= ĠMutable List ( m ) Ġ{ ĠMutable List ( n ) Ġ{ Ġ 0 Ġ} Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠ Ġpositions . forEach Ġ{ Ġ( row , Ġcol ) Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( grid [ row ][ col ] Ġ!= Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġind Ġ= Ġget Index ( row , Ġcol , Ġn ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgrid [ row ][ col ] Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġunion Find . add Tree ( ind ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( d Ġin Ġ 0 Ġuntil Ġ 4 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn Row Ġ= Ġrow Ġ+ Ġdi [ d ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn Col Ġ= Ġcol Ġ+ Ġdj [ d ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( n Row Ġ>= Ġ 0 Ġ&& Ġn Col Ġ>= Ġ 0 Ġ&& Ġn Row Ġ< Ġm Ġ&& Ġn Col Ġ< Ġn Ġ&& Ġgrid [ n Row ][ n Col ] Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġunion Find . union ( ind , Ġget Index ( n Row , Ġn Col , Ġn )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( union Find . fore sts ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġget Index ( row : ĠInt , Ġcol : ĠInt , Ġm : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġrow Ġ* Ġm Ġ+ Ġcol ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġclass ĠUnion Find Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġrank Ġ= Ġhash Map Of < Int , ĠInt >() ĊĠĠĠĠĠĠĠ Ġval Ġparent Ġ= Ġhash Map Of < Int , ĠInt >() ĊĠĠĠĠĠĠĠ Ġvar Ġfore sts Ġ= Ġ 0 ĊĊĠĠĠĠĠĠĠ Ġfun Ġadd Tree ( node : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrank [ node ] Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġparent [ node ] Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfore sts ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġfind ( node : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġparent [ node ]) Ġreturn Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfind ( parent [ node ] !! ). also Ġ{ Ġparent [ node ] Ġ= Ġit Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġlink ( node 1 : ĠInt , Ġnode 2 : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġx Ġ= Ġnode 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġy Ġ= Ġnode 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( rank [ x ] !! Ġ> Ġrank [ y ] !! ) Ġx Ġ= Ġy . also Ġ{ Ġy Ġ= Ġx Ġ} Ġ// Ġswap ĊĠĠĠĠĠĠĠĠĠĠĠ Ġparent [ x ] Ġ= Ġy ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( rank [ x ] Ġ== Ġrank [ y ]) Ġrank [ y ] Ġ= Ġrank . get OrDefault ( y , Ġ 1 ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġunion ( node 1 : ĠInt , Ġnode 2 : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp 1 Ġ= Ġfind ( node 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp 2 Ġ= Ġfind ( node 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( p 1 Ġ!= Ġp 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlink ( p 1 , Ġp 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfore sts -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }