package ĠQ 2 Ċ Ċ import Ġjava . nio . file . Files Ċ import Ġjava . nio . file . Paths Ċ Ċ val ĠANSI _ RESET Ġ= Ġ"\ u 0 0 1 B [ 0 m " Ċ val ĠANSI _ BLACK Ġ= Ġ"\ u 0 0 1 B [ 3 0 m " Ċ val ĠANSI _ RED Ġ= Ġ"\ u 0 0 1 B [ 3 1 m " Ċ val ĠANSI _ GREEN Ġ= Ġ"\ u 0 0 1 B [ 3 2 m " Ċ val ĠANSI _ YELLOW Ġ= Ġ"\ u 0 0 1 B [ 3 3 m " Ċ val ĠANSI _ BLUE Ġ= Ġ"\ u 0 0 1 B [ 3 4 m " Ċ val ĠANSI _ PUR PLE Ġ= Ġ"\ u 0 0 1 B [ 3 5 m " Ċ val ĠANSI _ CY AN Ġ= Ġ"\ u 0 0 1 B [ 3 6 m " Ċ val ĠANSI _ WHITE Ġ= Ġ"\ u 0 0 1 B [ 3 7 m " Ċ Ċ fun Ġmain ( args : ĠArray < String >) Ġ{ ĊĠ Ġvar Ġfile _ name Ġ= Ġargs . getOrElse ( 0 ) Ġ{ Ġ" matrix . txt " Ġ} ĊĠ Ġwhile Ġ( Files . not Exists ( Paths . get ( file _ name ))) Ġ{ ĊĠĠĠ Ġfile _ name Ġ= Ġ{ ĊĠĠĠĠĠ Ġprintln (" è¾ĵåħ¥ æĸĩä»¶ ç»Ŀ å¯¹ è·¯å¾Ħ ") ĊĠĠĠĠĠ Ġprintln (" æ³¨æĦı Windows åĴĮ Unix è·¯å¾Ħ åĪĨ éļĶ ç¬¦ ï¼Į æİ¨èįĲ ä½¿çĶ¨ æŃ£ æĸ ľ æĿ ł /") ĊĠĠĠĠĠ Ġprintln (" æĸĩä»¶ åĨħ æľī å¤ļ è¡Į ") ĊĠĠĠĠĠ Ġprintln (" æ¯ı è¡Į æľī ç©º æł¼ åĪĨ å¼Ģ çļĦ ä¸¤ä¸ª æŃ£ æķ´æķ° ") ĊĠĠĠĠĠ Ġprintln (" åĪĨåĪ« ä»£è¡¨ çŁ©éĺµ çļĦ è¡Į ç»´ åº¦ åĴĮ åĪĹ ç»´ åº¦ ") ĊĠĠĠĠĠ Ġread Line () !! Ċ // ĠĠĠĠĠ Ġ" Y :/ matrix . txt " ĊĠĠĠ Ġ} () ĊĠ Ġ} ĊĊĠ Ġval Ġmatrices Ġ= Ġmutable ListOf < Pair < Int , ĠInt >>() ĊĠ Ġvar Ġlast : ĠInt ? Ġ= Ġnull ĊĠ Ġtry Ġ{ ĊĠĠĠ ĠPaths . get ( file _ name ). to File (). forEach Line Ġ{ ĊĊĠĠĠĠĠ Ġval Ġ( a , Ġb ) Ġ= Ġit . split ("\\ s +". to Regex ()). map Ġ{ Ġit . toInt () Ġ} ĊĊĠĠĠĠĠ Ġif Ġ( last ?. equals ( a )?. not () Ġ?: Ġ( false )) ĊĠĠĠĠĠĠĠ Ġthrow ĠArithmetic Exception (" è¾ĵåħ¥ : Ġ$ it , Ġ çĽ¸ éĤ » çŁ©éĺµ ç»´ åº¦ ä¸į ç¬¦åĲĪ ä¹ ĺ æ³ķ è§ĦåĪĻ , Ġä¸Ĭ ä¸Ģä¸ª çŁ©éĺµ çļĦ åĪĹ æķ° ä¸º $ last ") ĊĠĠĠĠĠ Ġlast Ġ= Ġb ĊĠĠĠĠĠ Ġmatrices Ġ+= ĠPair ( a , Ġb ) ĊĠĠĠ Ġ} ĊĠ Ġ} Ġcatch Ġ( e : ĠException ) Ġ{ ĊĠĠĠ Ġwhen Ġ( e ) Ġ{ ĊĠĠĠĠĠ Ġis ĠArithmetic Exception Ġ-> Ġthrow Ġe ĊĠĠĠĠĠ Ġis ĠNumber FormatException Ġ-> Ġthrow ĠIllegalArgumentException ("${ e . localized Message }, Ġ è§£æŀĲ éĶĻè¯¯ , Ġ åĮħåĲ« éĿŀ æķ°åŃĹ ") ĊĠĠĠĠĠ Ġelse Ġ-> Ġthrow ĠIllegalArgumentException (" è§£æŀĲ éĶĻè¯¯ , Ġ è¾ĵåħ¥ ä¸į ç¬¦åĲĪ è§ĦåĪĻ ") ĊĠĠĠ Ġ} ĊĠ Ġ} ĊĊĠ Ġprintln (" matrix s Ġ= Ġ${ matrices }") ĊĊĠ Ġ/* ä¹ ĺ æ³ķ æ¬¡æķ° çºª å½ķ */ ĊĠ Ġval Ġcost _ array Ġ= ĠArray ( matrices . size ) Ġ{ ĠInt Array ( matrices . size ) Ġ} ĊĠ Ġ/* åĪĩ åĪĨ çĤ¹ ï¼Į ( i , Ġj ) ä½įç½® ä¸Ĭ åĢ¼ k çļĦ æĦı æĢĿ æĺ¯ Ġ åĪĩ åĪĨ æĪĲ [ i : k ], Ġ[ k + 1 : j ] ä¸¤ éĥ¨åĪĨ çĽ¸ ä¹ ĺ */ ĊĠ Ġval Ġsplit _ array Ġ= ĠArray ( matrices . size ) Ġ{ ĠInt Array ( matrices . size ) Ġ} ĊĠ Ġ/* çŁ©éĺµ ç»´ åº¦ å¤§å°ı ï¼Į ç¬¬ i ä¸ª çŁ©éĺµ çļĦ è¡Į åĪĹ æķ° åľ¨ < i , i + 1 > çļĦ ä½įç½® ä¸Ĭ */ ĊĠ Ġval Ġdimension Ġ= ĠInt Array ( matrices . size Ġ+ Ġ 1 ) Ġ{ Ġmatrices . getOrElse ( it , Ġ{ ĠPair ( matrices . last (). second , Ġ 0 ) Ġ}). first Ġ} ĊĊĠ Ġfun ĠLook Up Chain ( i : ĠInt , Ġj : ĠInt ): ĠInt Ġ{ ĊĠĠĠ Ġ// ä¹ ĺ æ³ķ åħĥç´ł åıªæľī ä¸Ģä¸ª çŁ©éĺµ æĹ¶çļĦ æĥħåĨµ ĊĠĠĠ Ġif Ġ( i Ġ== Ġj ) Ġreturn Ġ 0 ĊĊĠĠĠ Ġ// å¦Ĥæŀľ å·²ç»ı è®¡ç®Ĺ è¿ĩ äºĨ ĊĠĠĠ Ġif Ġ( cost _ array [ i ][ j ] Ġ> Ġ 0 ) Ġreturn Ġcost _ array [ i ][ j ] ĊĊĠĠĠ Ġval Ġtmp _ lint Ġ= Ġ( i Ġuntil Ġj ). map Ġ{ Ġk Ġ-> ĊĠĠĠĠĠ Ġ// çŁ©éĺµ è¿ŀ ä¹ ĺ A [ i : j ] åĪĨ åī² æĪĲ A [ i : k ] åĴĮ A [ k + 1 : j ] ä¸¤ä¸ª çŁ©éĺµ çļĦ åħ¨ æĭ¬ åı· æĸ¹å¼ı ĊĠĠĠĠĠ ĠLook Up Chain ( i , Ġk ) Ġ+ ĠLook Up Chain ( k Ġ+ Ġ 1 , Ġj ) Ġ+ Ġdimension [ i ] Ġ* Ġdimension [ k Ġ+ Ġ 1 ] Ġ* Ġdimension [ j Ġ+ Ġ 1 ] ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġmin Ġ= Ġtmp _ lint . min () !! ĊĠĠĠ Ġsplit _ array [ i ][ j ] Ġ= Ġtmp _ lint . indexOf ( min ) Ġ+ Ġi ĊĠĠĠ Ġcost _ array [ i ][ j ] Ġ= Ġmin ĊĠĠĠ Ġreturn Ġmin ĊĠ Ġ} ĊĊĠ Ġprintln (" æľĢå°ı éľĢè¦ģ ï¼ļ" Ġ+ ĠLook Up Chain ( 0 , Ġmatrices . size Ġ- Ġ 1 )) Ġ// Ġ åı³ ä¸Ĭ è§Ĵ çļĦ åħĥç´ł ĊĊĠ Ġfun Ġmake _ matrix _ color ful ( s : ĠString , Ġcolor : ĠString ): ĠString Ġ= ĊĠĠĠĠĠ Ġcolor Ġ+ Ġs Ġ+ ĠANSI _ RESET ĊĊĠ Ġfun Ġtrace _ back ( i : ĠInt , Ġj : ĠInt ): ĠString Ġ{ ĊĠĠĠ Ġif Ġ( i Ġ== Ġj ) ĊĠĠĠĠĠ Ġreturn Ġmake _ matrix _ color ful ( array Of ( i , Ġi Ġ+ Ġ 1 ). join ToString (" ÃĹ ", Ġ"[", Ġ"] ") Ġ{ Ġdimension [ it ]. toString () Ġ}, ĠANSI _ BLUE ) ĊĊĠĠĠ Ġval Ġsplit _ point Ġ= Ġsplit _ array [ i ][ j ] Ġ// Ġ è¿ŀ ä¹ ĺ åĪĨ åī² çĤ¹ ĊĠĠĠ Ġval Ġleft Ġ= Ġtrace _ back ( i , Ġsplit _ point ) Ġ// Ġ[ i : Ġk ] ĊĠĠĠ Ġval Ġright Ġ= Ġtrace _ back ( split _ point Ġ+ Ġ 1 , Ġj ) Ġ// Ġ[ k + 1 : Ġj ] ĊĊĠĠĠ Ġreturn Ġ" (% s Ġ* Ġ% s ) ". format ( left , Ġright ) ĊĊĠ Ġ} ĊĊĠ Ġprintln ( trace _ back ( 0 , Ġmatrices . size Ġ- Ġ 1 )) Ċ } ĊĊĊĊ