package Ġdays Ċ Ċ import Ġjava . util .* Ċ Ċ class ĠDay 1 5 Ġ: ĠDay ( 1 5 ) Ġ{ ĊĠĠĠ Ġprivate Ġval Ġdi Ġ= ĠlistOf (- 1 , Ġ 0 , Ġ 0 , Ġ 1 ) ĊĠĠĠ Ġprivate Ġval Ġdj Ġ= ĠlistOf ( 0 , Ġ- 1 , Ġ 1 , Ġ 0 ) ĊĊĊĠĠĠ Ġoverride Ġfun Ġpart One (): ĠAny Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmap Ġ= Ġinput List . map Ġ{ Ġit . map Ġ{ ĠCharacter . get Numeric Value ( it ) Ġ} Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfind Path ( map ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġpart Two (): ĠAny Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmap Ġ= Ġinput List . map Ġ{ Ġit . map Ġ{ ĠCharacter . get Numeric Value ( it ) Ġ} Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġ( n , Ġm ) Ġ= Ġmap . size Ġto Ġmap . first (). size ĊĠĠĠĠĠĠĠ Ġval Ġextended Ġ= ĠArray ( n Ġ* Ġ 5 ) Ġ{ ĠArray ( m Ġ* Ġ 5 ) Ġ{ Ġ 0 Ġ} Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn Ġ* Ġ 5 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 Ġuntil Ġm Ġ* Ġ 5 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdist From Source Ġ= Ġi Ġ/ Ġn Ġ+ Ġj Ġ/ Ġm ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ( src I , Ġsrc J ) Ġ= Ġi Ġ% Ġn Ġto Ġj Ġ% Ġm ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġextended [ i ][ j ] Ġ= Ġ 1 Ġ+ Ġ( map [ src I ][ src J ] Ġ+ Ġdist From Source Ġ- Ġ 1 ) Ġ% Ġ 9 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfind Path ( extended . map Ġ{ Ġit . toList () Ġ}) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġfind Path ( map : ĠList < List < Int >> ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġqueue Ġ= ĠPriority Queue < Path Entry >() ĊĠĠĠĠĠĠĠ Ġval Ġdist To Ġ= ĠArray ( map . size ) Ġ{ ĠArray ( map . first (). size ) Ġ{ Ġ- 1 Ġ} Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġstart Ġ= Ġ 0 Ġto Ġ 0 ĊĠĠĠĠĠĠĠ Ġval Ġend Ġ= Ġmap . size Ġ- Ġ 1 Ġto Ġmap . first (). size Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġqueue . add ( Path Entry ( 0 , Ġstart . first , Ġstart . second )) ĊĠĠĠĠĠĠĠ Ġdist To [ start . first ][ start . second ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ( dist , Ġi , Ġj ) Ġ= Ġqueue . poll () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ(( di i , Ġd jj ) Ġin Ġdi . zip ( dj )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( i Ġ+ Ġdi i Ġin Ġmap . indices Ġ&& Ġj Ġ+ Ġd jj Ġin Ġmap . first (). indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġprev Dist Ġ= Ġdist To [ i Ġ+ Ġdi i ][ j Ġ+ Ġd jj ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( prev Dist Ġ== Ġ- 1 Ġ|| Ġprev Dist Ġ> Ġdist Ġ+ Ġmap [ i Ġ+ Ġdi i ][ j Ġ+ Ġd jj ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( prev Dist Ġ!= Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . remove If Ġ{ Ġit . i Ġto Ġit . j Ġ== Ġi Ġ+ Ġdi i Ġto Ġj Ġ+ Ġd jj Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdist To [ i Ġ+ Ġdi i ][ j Ġ+ Ġd jj ] Ġ= Ġdist Ġ+ Ġmap [ i Ġ+ Ġdi i ][ j Ġ+ Ġd jj ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . add ( Path Entry ( dist To [ i Ġ+ Ġdi i ][ j Ġ+ Ġd jj ], Ġi Ġ+ Ġdi i , Ġj Ġ+ Ġd jj )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġdist To [ end . first ][ end . second ] ĊĠĠĠ Ġ} ĊĊĊĠĠĠ Ġdata Ġclass ĠPath Entry ( val Ġdistance : ĠInt , Ġval Ġi : ĠInt , Ġval Ġj : ĠInt ): ĠComparable < Path Entry > Ġ{ ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġcompare To ( other : ĠPath Entry ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġdistance . compareTo ( other . distance ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ