package Ġcom . k ish or . kotlin . algo . algorithms . graph Ċ Ċ import Ġjava . util . HashSet Ċ import Ġjava . util . LinkedList Ċ import Ġjava . util . Queue Ċ import Ġjava . util . Deque Ċ import Ġjava . util . HashMap Ċ Ċ internal Ġclass ĠMin K night Moves Ġ{ ĊĊĠĠĠ Ġfun Ġmin K night Moves ( x : ĠInt , Ġy : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġx Ġ= Ġx ĊĠĠĠĠĠĠĠ Ġvar Ġy Ġ= Ġy ĊĠĠĠĠĠĠĠ Ġx Ġ= ĠMath . abs ( x ) ĊĠĠĠĠĠĠĠ Ġy Ġ= ĠMath . abs ( y ) ĊĠĠĠĠĠĠĠ Ġif Ġ( x Ġ== Ġ 0 Ġ&& Ġy Ġ== Ġ 0 ) Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġval Ġqueue : ĠQueue < Pair < Int , ĠInt >> Ġ= ĠLinkedList () ĊĠĠĠĠĠĠĠ Ġval Ġset : ĠMutable Set < Pair < Int , ĠInt >> Ġ= ĠHashSet () ĊĠĠĠĠĠĠĠ Ġqueue . add ( Pair ( 0 , Ġ 0 )) ĊĠĠĠĠĠĠĠ Ġset . add ( queue . peek ()) ĊĠĠĠĠĠĠĠ Ġval Ġdirs Ġ= ĠarrayOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 2 , Ġ 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf (- 2 , Ġ 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 2 , Ġ- 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf (- 2 , Ġ- 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 1 , Ġ 2 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf (- 1 , Ġ 2 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 1 , Ġ- 2 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf (- 1 , Ġ- 2 ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġvar Ġlevel Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ(! queue . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsize Ġ= Ġqueue . size ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġsize ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġparent Ġ= Ġqueue . poll () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( dir Ġin Ġdirs ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx 0 : ĠInt Ġ= ĠMath . abs ( parent . first Ġ+ Ġdir [ 0 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġy 0 : ĠInt Ġ= ĠMath . abs ( parent . second Ġ+ Ġdir [ 1 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( x 0 Ġ== Ġx Ġ&& Ġy 0 Ġ== Ġy ) Ġreturn Ġlevel Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġchild Ġ= ĠPair ( x 0 , Ġy 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! set . contains ( child )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset . add ( child ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . add ( child ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlevel ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġlevel ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġmin K night Moves Using Array ( x : ĠInt , Ġy : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġthe Ġoffsets Ġin Ġthe Ġeight Ġdirections ĊĠĠĠĠĠĠĠ Ġval Ġoffsets Ġ= ĠarrayOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 1 , Ġ 2 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 2 , Ġ 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 2 , Ġ- 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 1 , Ġ- 2 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf (- 1 , Ġ- 2 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf (- 2 , Ġ- 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf (- 2 , Ġ 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf (- 1 , Ġ 2 ) ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġ// Ġ- ĠR ather Ġthan Ġusing Ġthe Ġin efficient ĠHashSet , Ġwe Ġuse Ġthe Ġbitmap ĊĠĠĠĠĠĠĠ Ġ// ĠĠĠĠ Ġotherwise Ġwe Ġwould Ġrun Ġout Ġof Ġtime Ġfor Ġthe Ġtest Ġcases . ĊĠĠĠĠĠĠĠ Ġ// Ġ- ĠWe Ġcreate Ġa Ġbitmap Ġthat Ġis Ġsufficient Ġto Ġcover Ġall Ġthe Ġpossible ĊĠĠĠĠĠĠĠ Ġ// ĠĠĠĠ Ġinputs , Ġaccording Ġto Ġthe Ġdescription Ġof Ġthe Ġproblem . ĊĠĠĠĠĠĠĠ Ġval Ġvisited Ġ= ĠArray ( 6 0 5 ) Ġ{ ĠBoolean Array ( 6 0 5 ) Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġqueue : ĠDe que < IntArray > Ġ= ĠLinkedList () ĊĠĠĠĠĠĠĠ Ġqueue . add Last ( int ArrayOf ( 0 , Ġ 0 )) ĊĠĠĠĠĠĠĠ Ġvar Ġsteps Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( queue . size Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcurr Level Size Ġ= Ġqueue . size ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġiterate Ġthrough Ġthe Ġcurrent Ġlevel ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġcurr Level Size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcurr Ġ= Ġqueue . remove First () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( curr [ 0 ] Ġ== Ġx Ġ&& Ġcurr [ 1 ] Ġ== Ġy ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġsteps ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( offset Ġin Ġoffsets ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnext Ġ= Ġint ArrayOf ( curr [ 0 ] Ġ+ Ġoffset [ 0 ], Ġcurr [ 1 ] Ġ+ Ġoffset [ 1 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġalign Ġthe Ġcoordinate Ġto Ġthe Ġbitmap ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! visited [ next [ 0 ] Ġ+ Ġ 3 0 2 ][ next [ 1 ] Ġ+ Ġ 3 0 2 ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvisited [ next [ 0 ] Ġ+ Ġ 3 0 2 ][ next [ 1 ] Ġ+ Ġ 3 0 2 ] Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . add Last ( next ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsteps ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġmove Ġon Ġto Ġthe Ġnext Ġlevel ĊĠĠĠĠĠĠĠ Ġreturn Ġsteps ĊĠĠĠ Ġ} Ċ Ċ // ĠDFS ĊĊĠĠĠ Ġprivate Ġval Ġmemo : ĠMutable Map < String , ĠInt ?> Ġ= ĠHashMap () ĊĊĠĠĠ Ġprivate Ġfun Ġdfs ( x : ĠInt , Ġy : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġkey Ġ= Ġ"$ x ,$ y " ĊĠĠĠĠĠĠĠ Ġif Ġ( memo . containsKey ( key )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġmemo [ key ] !! ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( x Ġ+ Ġy Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( x Ġ+ Ġy Ġ== Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 2 ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġret Ġ= ĠMath . min ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdfs ( Math . abs ( x Ġ- Ġ 1 ), ĠMath . abs ( y Ġ- Ġ 2 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdfs ( Math . abs ( x Ġ- Ġ 2 ), ĠMath . abs ( y Ġ- Ġ 1 )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmemo [ key ] Ġ= Ġret ĊĠĠĠĠĠĠĠĠĠĠĠ Ġret ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġmin K night Moves D fs ( x : ĠInt , Ġy : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġdfs ( Math . abs ( x ), ĠMath . abs ( y )) ĊĠĠĠ Ġ} Ċ }