package Ġus . j wf . a oc 2 0 2 1 Ċ Ċ import Ġjava . io . Reader Ċ import Ġjava . util . Priority Queue Ċ import Ġus . j wf . a oc . Day Ċ Ċ /** Ċ Ġ* ĠA o C Ġ 2 0 2 1 Ġ- ĠDay Ġ 1 5 Ċ Ġ*/ Ċ class ĠDay 1 5 Ch iton Ġ: ĠDay < Int , ĠInt > Ġ{ ĊĠ Ġoverride Ġsuspend Ġfun Ġexecute Part 1 ( input : ĠReader ): ĠInt Ġ{ ĊĠĠĠ Ġval Ġlines Ġ= Ġinput . read Lines () ĊĠĠĠ Ġval Ġgrid Ġ= ĠArray ( lines . size ) Ġ{ Ġlines [ it ]. map Ġ{ Ġit . digit ToInt () Ġ}. to IntArray () Ġ} ĊĠĠĠ Ġreturn Ġmin Distance ( grid ) ĊĠ Ġ} ĊĊĠ Ġoverride Ġsuspend Ġfun Ġexecute Part 2 ( input : ĠReader ): ĠInt Ġ{ ĊĠĠĠ Ġval Ġlines Ġ= Ġinput . read Lines () ĊĠĠĠ Ġval Ġorig Ġ= ĠArray ( lines . size ) Ġ{ Ġlines [ it ]. map Ġ{ Ġit . digit ToInt () Ġ}. to IntArray () Ġ} ĊĠĠĠ Ġval Ġgrid Ġ= ĠArray ( lines . size Ġ* Ġ 5 ) Ġ{ Ġgy Ġ-> ĊĠĠĠĠĠ ĠInt Array ( lines [ 0 ]. length Ġ* Ġ 5 ) Ġ{ Ġgx Ġ-> ĊĠĠĠĠĠĠĠ Ġval Ġo y Ġ= Ġgy Ġ% Ġlines . size ĊĠĠĠĠĠĠĠ Ġval Ġox Ġ= Ġgx Ġ% Ġlines [ 0 ]. length ĊĠĠĠĠĠĠĠ Ġval ĠnewValue Ġ= Ġorig [ oy ][ ox ] Ġ+ Ġgy Ġ/ Ġlines . size Ġ+ Ġgx Ġ/ Ġlines [ 0 ]. length ĊĠĠĠĠĠĠĠ Ġif Ġ( newValue Ġ% Ġ 9 Ġ== Ġ 0 ) Ġ 9 Ġelse ĠnewValue Ġ% Ġ 9 ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġmin Distance ( grid ) ĊĠ Ġ} ĊĊĠ Ġfun Ġmin Distance ( grid : ĠArray < IntArray >): ĠInt Ġ{ ĊĠĠĠ Ġval Ġqueue Ġ= ĊĠĠĠĠĠ ĠPriority Queue < Pos > Ġ{ Ġa , Ġb Ġ-> Ġa . risk Ġ- Ġb . risk Ġ} ĊĠĠĠĠĠĠĠ Ġ. apply Ġ{ Ġadd ( Pos ( Point ( 0 , Ġ 0 ), Ġ 0 )) Ġ} ĊĠĠĠ Ġval Ġvisited Ġ= Ġmutable Set Of ( Point ( 0 , Ġ 0 )) ĊĊĠĠĠ Ġval Ġtarget Ġ= ĠPoint ( grid [ 0 ]. size Ġ- Ġ 1 , Ġgrid . size Ġ- Ġ 1 ) ĊĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠ Ġval Ġcurrent Ġ= Ġqueue . poll () ĊĠĠĠĠĠ Ġif Ġ( current . point Ġ== Ġtarget ) Ġreturn Ġcurrent . risk ĊĊĠĠĠĠĠ Ġval Ġcurrent Point Ġ= Ġcurrent . point ĊĠĠĠĠĠ Ġval Ġ( cx , Ġcy ) Ġ= Ġcurrent Point ĊĠĠĠĠĠ Ġif Ġ( current Point . y Ġ+ Ġ 1 Ġ< Ġgrid . size ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdown Ġ= ĠPos ( ĊĠĠĠĠĠĠĠĠĠ Ġpoint Ġ= ĠPoint ( cx , Ġcy Ġ+ Ġ 1 ), ĊĠĠĠĠĠĠĠĠĠ Ġrisk Ġ= Ġcurrent . risk Ġ+ Ġgrid [ cy Ġ+ Ġ 1 ][ cx ] ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġif Ġ( down . point Ġ! in Ġvisited ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġvisited . add ( down . point ) ĊĠĠĠĠĠĠĠĠĠ Ġqueue . add ( down ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġif Ġ( current Point . y Ġ- Ġ 1 Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġup Ġ= ĠPos ( ĊĠĠĠĠĠĠĠĠĠ Ġpoint Ġ= ĠPoint ( cx , Ġcy Ġ- Ġ 1 ), ĊĠĠĠĠĠĠĠĠĠ Ġrisk Ġ= Ġcurrent . risk Ġ+ Ġgrid [ cy Ġ- Ġ 1 ][ cx ] ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġif Ġ( up . point Ġ! in Ġvisited ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġvisited . add ( up . point ) ĊĠĠĠĠĠĠĠĠĠ Ġqueue . add ( up ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġif Ġ( current Point . x Ġ+ Ġ 1 Ġ< Ġgrid [ 0 ]. size ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġright Ġ= ĠPos ( ĊĠĠĠĠĠĠĠĠĠ Ġpoint Ġ= ĠPoint ( cx Ġ+ Ġ 1 , Ġcy ), ĊĠĠĠĠĠĠĠĠĠ Ġrisk Ġ= Ġcurrent . risk Ġ+ Ġgrid [ cy ][ cx Ġ+ Ġ 1 ] ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġif Ġ( right . point Ġ! in Ġvisited ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġvisited . add ( right . point ) ĊĠĠĠĠĠĠĠĠĠ Ġqueue . add ( right ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġif Ġ( current Point . x Ġ- Ġ 1 Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġleft Ġ= ĠPos ( ĊĠĠĠĠĠĠĠĠĠ Ġpoint Ġ= ĠPoint ( cx Ġ- Ġ 1 , Ġcy ), ĊĠĠĠĠĠĠĠĠĠ Ġrisk Ġ= Ġcurrent . risk Ġ+ Ġgrid [ cy ][ cx Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġif Ġ( left . point Ġ! in Ġvisited ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġvisited . add ( left . point ) ĊĠĠĠĠĠĠĠĠĠ Ġqueue . add ( left ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġ 0 ĊĠ Ġ} ĊĊĠ Ġdata Ġclass ĠPoint ( val Ġx : ĠInt , Ġval Ġy : ĠInt ) ĊĠ Ġdata Ġclass ĠPos ( val Ġpoint : ĠPoint , Ġval Ġrisk : ĠInt ) Ċ }