+123221331113123234423344224431433133532552524541132342115251533353444125345313143145531512422141211453241324522431114333434123331432212313332

+332131211221231334113411434314221234212544551343434424414522444514152321235333114535111213325543341434455452433231244111211333244141323221333

+332312121124213132132332334142515313244424114442531354342155112224213345233521322352411122352523114244424243243144322423112424324232313211221

+232232313332123124343233134235522312451423132245432243213243563634463633646355462432112511341144332554542152451251242134333223242411123132123

+321221333423241244344444113235132444533212244411215521544364256422356332324522345523352545514432231115552121221554343223141143123324241221131

+212323323144242312432122115135411352441215352252455266233334356222542336523262522223264322224312241225552553254525531241321113321223144323133

+313331134114444233331444524353153425324213511311144322625564662524335456266324646442432434622434144243322232314121531214421213332233123112223

+231212312331434432223111315233424152535425353432564454634345624363335365224454264426624345633443253145522412335542513124241223411441412122111

+222312342221232323321325334353233342515153346442633345256366445236565634246242622232236243255353335225324415435552551511113124142341124323213

+333234324211211414343321212512534152115552556642235365623345233556244346533226665426346664533652426445412144141335141315423444441414142133413

+132424441133214421133443125113143223235552362343236652633642646423424622433626535252336462254566342664315453451515455235355514142232213232413

+233341124313112342125432331422441115414265226553433526453342352235542623345344326442526226354666463553454521413523324334425531211211412231232

+334132332331331145252312342114334344534263562234242432453354263623343534453563545565324542453462653333256533553252422321341111411214442321443

+432114424311224241131224335131154552233563256663366456553364326624533536452333445426222425343246625426423344344345214134344334214423341222234

+421442431221312233122251345112313543446462633446255243625366636335747635645636624253435366223253633463663553552111415443442413531342342213442

+232431131114123455332324341125334543333254354236445333562626334766355656674643653444262262263222555625432352532455521125241125331142131424433

+121411343143134214134514121231556326565562433645232244643376567655346446337467474437365345545634434665552624662533133431513514113432432341334

+243314413243512322312121524255363424544246256635624545575366643737473643535775744347733736446352332434523436335532153433515112122534112244322

+314143244143145532132153214134544534242265436646435564636336463756675477356433737466667577547625336643224223333646515512512534551221411223134

+121121221435142554551353224566223643235552644326654633533533557665575355763375563555744533765336334245356522245566433332232345112251212431131

+244112233213145441231513422363545625565334464333463373743576565557433364333353646454755434755433754356442332326633246551235125544424212223122

+422231444221415235544514233236523544246226566343577656475444373664455747776355744477664576474756635755366525332663322354522115444231421321431

+144223345543134152354436532333364325565452655546467533534767565534367646444577754755735554365553663355224264234625323626254155154555543443124

+123314352211145434244225546566464464255657654736556356756364444446666347435356775464757557337745353436722354545533544264351343113314453122113

+124113454134314132542662542452456245433775466766676346773464533464734575544657344647333555336464573467334433433322366222625523242545544422221

+313234534454155321146565323255224343434566437354677537743557744674776573733333475353454573537667475735636463264333453566466451425445134314211

+111222325451233154435554533233322662345574546353364647765636363554685447876774457636744464557633636375757665364524456234542512225152354415133

+314312152252132424242653565653522523455346645466545336745376755465844687475674475664734376554373343546456436632233535444634451134353134243141

+134435541321441522666434533355346336733335467666644575546467466548877574765675855575687435354634735774455374554653652636564565353453131535522

+342533451223542535446346652434364664766666565543567744587447774645558888776758657577648586636765363335437654475525464366223262451215214533221

+322452515431424523543335524332553774363664457375335845685684445745587677564454864767686565664474653466655535747433664343536533541545424435353

+114241242535421163253623532254677347735367563455387664674745446666568666666665548546645856754856563737456764553765252352423662314312544423345

+124312211551155232453434536545765767345577367736767545657656678847564464854586477758554558758457555675667456766636545253433466351343543435553

+411241513354153336534335465646545556535673633487584784686884475757648757874488665748477888566786455445756653537536636232622366325123144335145

+143213345152335235432264456354545744755676367445688645555844588766545568747687476854766768847455556447444777764375344226526534266515122241341

+212244332513334532636354655457645645563673364585748844854485644787875664675588478844676585858786778446656655567377542433345542554225541431255

+212522122332435522256662535376657667364447557467467667885857465678648764687878755648886754648558546877543344635534447425432346544552114554234

+315313445532346443366633365665656676634738848576865574585674466865579657595786778445746875666888644676635365364774666665426522565635325313253

+241333421536452523554233277376756643376488654678767846584657855569799879565796957655457866458588486875677736377736646346336543223352252435432

+445531334134456235526555753677757443737858867567864688685889789865775865967888587577458445668856755844666544544433456664533566452543154341122

+354343314446543535265643747575673456548475445875766576485957995569998756777666589795956547554747585887587543754557456334262352422464525543211

+112243325155352362655244455657555537377848665474847676765797557977959679587686859679999686557446865787458856657676635345542365654545543251342

+425124241326443426646576363573454545858474447587478677585895597679955855756989576575879579577548854767845483373364733667335244542526653245444

+454235534452232326556767435675774737886566666544754866899896799967977557787785656565965758878447876474787847446573334767555424365232331351313

+544241123466336355224454474344564747474448765546779897755585666577786979959855965998779886976568847488878748633533446645474222223226432443532

+343232524652246324454373467356555688547657566648799975569897786896885957856779797677987959875887766675587686673576646466764263433354225412244

+455341525454453432527473737466773774857576477448898565696789697875989789596788578695588757786554646786857776463434674733746356332324633223554

+453114146523525464543754753474338586786487464767787857998855569699997876759575985759587657978686484587685574446535634557557463345364433323353

+135221256565332664237533544633378687748576884498979869857776796795569775558965559997865877957556676478476757477775764737457624466532324523124

+442542332534466565477536747576586466574445686758966998878658775858677967776676759968556559569866585844577864654636553653374424435233244655152

+331142343325443336353753543733446587455644888855675679896757668897999789968796978688965686896889656788555476877473464364667535466453666624232

+225332325243433562676445757466476488486567688685589687566577677969969967867787687699968855656558697887456586856565763455456562222353522665455

+122233223362634263565635556643585887444677697895555799799597666969997698968977868787686986756879977764486764766863435673573544332265452465215

+323413454644464324434756657577756777884864696888666885866678699699798699889787868798988885677978689894844444465844534736357643242453224344532

+521445453542532557435566657464787558866588975756758689659698789776686988797878979866899665977557686697576455868656656745563333525644263424533

+542155336435226676567344443538866876486489679755667759599869878876986676696986687677699878689879589768756687587758547535564734655232363632412

+521142342222434346346543435565468788744566796968777995889666976779778999998888677788789675665675559769466778885845663345437736563423536322434

+114465225364655534634534356444875647876766687789597666698676686886799898966797667999868867685875578698966744446466563553537375726566645356642

+455324424625634363436774636685848445547685899958667698899688787788869697899896969798997796567657587665665554776474577344477373342444626635614

+422226322265563345657446357545576884766869576766887767988668697798897986697686967699877779989675867576665766866566447553735367343366663542343

+522124564525542547443776775556474457774786887555865699897797768798677797898766769668896889697955695675657757587884654753667744472556566354445

+414553325663343447477536546566748685656899798666655967979789899999887889888888899797967688986975675886597747564644657334354645643325325535254

+312442523532256743477746345664768584458897689786569967786899889777987787799797988768979687879865579997569856444758744577365346662446325255565

+252463332344336366763666558488866445565765775585899979797687666877787787887789897676776669889795785585776548745784644564363574562652464564621

+351433465562632355675644565568847565569678766576779879666989767978988897789799779899979987679856985697675785778857585637674563645255262256261

+435246324264236455364356736845758865855697999696577689996869877998899887879877779686799879697669998868755686775554666576654457645323634233554

+522352225343465554567755554655668455877796676898787887999998689998797878888788987889686669866766896995798845448584856773564734446252424456452

+443554246226353766756737774887448767677579889659579999966997778798889778889789787998799698769967757986877788488746686576744353673445264566552

+432243544336264675356654457586485867865976996779666678769897888787988998777989779989896766688889699759556858786848766434734663466364653345244

+433366224565257743575366365847657668669695595796987779978677979777899987989997979786767766668878579955698756867787768357675344337423256246542

+552353555524335764376655444464848578669777778575788688888666898788789999999977779896999669978997577976895985887764887554757737476664223223561

+135424622234624657743544657664878876779697965675877779777969999988988979988899897888687978687798697979876574444565558344776777543333542353222

+244332226644237467336445746445784546769665698689578669867686799789997988898989778796878689786878558569798967585857475355467344677265362454655

+551454466366633374733467356568864588485886895886986667669688789998988777779888777887999799679677688769656585854456447437456747467246336325521

+254346346435456355743564458456656677777968675999899977997768997898898887788977877878798669998885858698799568547854746544464335747233533366334

+253263366546437375334745467456887458659796776598778777698699689878889788797797877798876689879968758987788958455478644467733343467635546364354

+351662265452245475535455536486857885795868897696886688896669789999799997997798887768868768796758896898576968856675778334367347656343452464653

+334243625235627555746543635854477644788597995695689979876888797879899977988798779867999669886989796997885578876556456434756435755546342346243

+411534254556336565767357465688777565878995789786696779786666898798879999797978779797676986986558898658598558865687456364457744676526526634661

+235346524222564664743453738677854858649659869687856696668977778798879887779898779778789886898565586568697485776847655335637545763444222445364

+343343262665245764763544553785888686469987885876558797786889978988879977878787769778978668667878656867698585446844766467767747674642323654432

+145433532622366446764634777878568646744595895868857776677869798989888988787877697968689787799889855888965568658666487533746663436624625364544

+223325666525625333753535333557556576784667695967877679688786696966789787777767787669667799675575887965654648445768577733467574355333362353324

+531353543635455645743766446687686464485695696798987786997769996686787996789889896998888998897867965665698774684786666536637474753646462626311

+224134245455443564347445766485684486575768976775658989996797686796696869796976797778788997566866768599866445547685555543454456365636544552232

+121125433236655653774743747357855548867599796786696779788768697998787987789687686688768767865597855676548858666444474775457653446223556634555

+432556343524653674566366757486867547566748655585676689699696669769977886767789999886978898767688767789756675856767443453457777554225425535421

+521215632555663334745454567438778644485745977666895699889999868689788899967798867667999955865997995578868585846677477664747746523222363465544

+441544366632652655655465665437764747677867958699889786798999786998697977789989996897979687555689688557467574465754563743377745625244663442121

+244433655255336546374754357534686447785555778558697797668866889668898799869877887987795599987896559666846778685758344357663754242546663533522

+415326345653222437635637344763557476488868475785999978559869999667996978976769896798658775695957896676578587766543634465565534543626636453315

+233135565242253222744546743437784877764744675985677897875688667686996779696998679668788757877976899658564758757447374777655566255552235631553

+455354565642255336576673367563586484567568787758596587979965787879969997777679899755765975977687755547445544686444753766565732235533226464353

+135245224656634556365665764357647858866584877576699879897576896988689769696889788756795568977658995647688684656856653365444656456434422221312

+442553552643562336533646743747454578875658554695668767868986975686955988879896868898589878888695577675886648456474645647757536324554233522134

+554155135243235326253475635375445587578484545655589758799687895568985859879678665889875879866688778788775554886734465657475343436533352331545

+513331233255554654637344364476366656887454576884779666666595595686956997556697876779686956798758856768568445556745365673473656355353263243233

+224555352553552436225455747433367375476447487456765879578758586676865687898675866856669677569544888867676478547745534465455544462654623135323

+343531542536226546656344377636574558547664664565768879579968986657699578578878968789975879776745588667748884744367335556663523225365252342234

+535414355453534236363474677665554645574567566856674657976768997779898967795875766859595855644487664458485765735334364465464535663266251111145

+324122333555662362654456773635354664455655588748575779586896858596857775996556587776689568558448445876748573454664477477752665355336262443231

+331135214563253564556535444374734745775564677786847484799956856788976888858975986876978668557488776878766465656763576773334656426535345455215

+212113254145323326332556477644343773457455667468675687647776988869585659766975795958755474556744584756658443474666337346626266654563624243445

+335123533414445226364322373673367576637468765565547754574879787878757858886967798989668556777745686766653757755765654342633532533325214313224

+152332225222643332336235273456467566445674756885884848684567755899668668986858578756684575486774858784857563735354646322453544344552215135443

+543243121531262353244453647377453653633645588677675758774846887858556568668864684586764656844784645785755664455543377344533326564531153211455

+341352542112425342565523355675365443653535676567755587454484457844546855445648566884464554778486768776645364767344664336552653563453322131443

+535115153315233552542664235776636374766534585656886758546488854465755866587865557474578448764858448437465375557674565244554255252515324545453

+144442242552246343665623365446756344736645536568474448786786576746475856646688588445474786655775844755753334767435353454543625532454131355242

+231213352415344465562435342226547636543675455675455745885675756578655886667646587655466574484675574345547373637747235365326254233221454135142

+413245325315123222664665443637767653773363337347885687768484854467448775755456567677675458868877666753667435763374244524455332533435152241224

+341213314355323432433645525262736374333555343644675474546878467754586557888588485686857477567745333557573553576434453222563352632112454323434

+121155532355355523244636534234454333636436653347553668444458486465688544485756677888468855487564765553646533354345652653225554324235324551155

+141243451121513146266455223345624347553366743756776378487854887686577577576568767545575578356346333655753474653245455333642542241121252453452

+321223154312544235244222236536342353663535437433476433754474675766557548468586768888446756447643744456334777466462245433354454522141145522134

+113211221342323112545626652526655256364666373567544474454654655656684585877654884487344767347354367773334776356546443254336421525145532224432

+444414443345242112454455452266535246445667343774653466544355657778744777447484645676555675766434347563574745636342233425522432151254323424331

+312243531213253122126323445624554223343737463367477633536473557775637653443537747475744575336747454436573545334232243346223222213113424232133

+344143325243234521144363342222533446654574436437573477344646466654765776566763454744454376746363536367766232442632434653424514154124243211123

+231441355353132442414142546226425653642275766736363547467766435745376347433435764546656743347467744435343462324424623256425322213431215134141

+322244213114121542124524546553534445236646677675676646655454755574474347665774473735733454563537433542632266322562563662425251235223135112141

+433214411435445514555113626532555325353432274347767654564344567674546367373543776755643765366657335654646426353264535663143413154354132241111

+433313332232425551235335166625645566362254236366673643357376733334633536453563457733353663676665755444423352524655346542555213454541113233134

+111434322435545555433341413546344654243453654455374543364477434453753434674666735656744746675444522242463334246542642542213515352221222142443

+433424223233135135325342554364223224266235236623243455545667557476375376735633765377443353336554425444464465656653323241133355314413324334133

+141123113311153144445231141333426264353655465564533275763565437436574565553566775764336643554333422434445536565553334431313142241211441144122

+313331214142322134334115212142445343324625456322424332647446546737647766765744465553477446633525543432254234353351253552555555151222311113133

+114333322314214443331444443423412552656564533663432355424443535547356477533335467473652644643323434645554644256113215225233245315421244334122

+423121232442311234323231553521541654342645435355635436323653442647567546775367654236644365245462532664432565664235243452212515521223322242231

+241313122233412433315111542533131523622623653623626442344435265344254652536234552542242354452443652265434536543442531332122123131322322141131

+312144322212212442433221143235344153445523326653432565454624225352322536533646663553346653432233436225242341152324231343545354321132314341331

+213412222433133412322313255335312354143354263524552543544346254652325234666453465336324364355224534322534524453444121252432154241332334121312

+331414122333122443141253124535534225131426346363422663625654444535662355335654664526533456633362565234635455254212332234214223143322431132111

+323334421423131221323331332252424225424551666332665326536555232545556343326365552222324665325334433545322334241234533442252122111443231342332

+133131134243143334123211252134553554115222242354566522232232326343222622464262534633243222233333363151423222321235321423213211112312414132312

+331322241144413232342341554322353432354541351135424226352253444442234433454563423356642554234646321214133113411143455455111424244411414123313

+332331131244233222224224231253155442224551514214353322345343642345642523566324255243332626634532135224144425312115351231141244121231341412333

+311322211311433441322224133353241353214331511213524245344525333533445633653423432536436253252142331255535221231143152112422243244431323213221

+122311232113144341241214232112233542445224314225551451215634543253222435656356365222623123523111213213421221341122352423142443333422312121313

+133212311332421131421414343131243241123151453114145545554214554345445565666324326225355141232331544243112552141221113442214312241243331111231

+131112221331242333321224411212253332222115454512512412123345511254214525534454555324153413522421232121224533451351311242134112424411231212233

+ let v = i.行().collect_vec();

+ let g = util::LMap::new(|(x, y, δx, δy, gone): (i16, i16, i16, i16, i16)| {

+ Some(

+ [

+ Dir::W + (x, y),

+ Dir::E + (x, y),

+ Dir::N + (x, y),

+ Dir::S + (x, y),

+ ]

+ .iter()

+ .filter_map(|&(nx, ny)| {

+ let ngon;

+ let nδx = nx - x;

+ let nδy = ny - y;

+ if nδx == δx && nδy == δy {

+ if gone == 3 {

+ return None;

+ }

+ ngon = gone + 1;

+ } else if (nδx == -δx && nδx != 0) || (nδy == -δy && nδy != 0) {

+ return None;

+ } else {

+ ngon = 1;

+ }

+ (nx >= 0 && nx < v[0].len() as i16 && ny >= 0 && ny < v.len() as i16).then(|| {

+ (

+ (nx, ny, nδx, nδy, ngon),

+ (v[ny as usize][nx as usize] - b'0') as u32,

+ )

+ })

+ })

+ .collect_vec(),

+ )

+ });

+ util::dijkstra(g, (0i16, 0i16, 0i16, 0i16, 0i16), |(x, y, _, _, _)| {

+ x == v[0].len() as i16 - 1 && y == v.len() as i16 - 1

+ })

+ cmp::Reverse,

+ collections::{hash_map::Entry, BinaryHeap, HashMap, HashSet},

+ fmt::{Debug, Write},

+ hash::Hash,

+ even, gcd, lcm, pa, Dir, GreekTools, IntoCombinations, IntoLines, IterͶ, NumTupleIterTools,

+#[repr(u8)]

+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Ord, PartialOrd)]

+pub enum Dir {

+ N,

+ E,

+ S,

+ W,

+}

+

+pub struct LMap<K, V, F>(HashMap<K, V>, F)

+where

+ F: Fn(K) -> Option<V>,

+ K: Eq + Hash + Copy;

+impl<K: Eq + Hash + Copy, V, F> LMap<K, V, F>

+where

+ F: Fn(K) -> Option<V>,

+{

+ pub fn new(f: F) -> Self {

+ Self {

+ 0: HashMap::new(),

+ 1: f,

+ }

+ }

+

+ pub fn get(&mut self, k: K) -> Option<&mut V> {

+ match self.0.entry(k) {

+ Entry::Occupied(x) => Some(x.into_mut()),

+ Entry::Vacant(e) => match self.1(k) {

+ Some(v) => Some(e.insert(v)),

+ None => None,

+ },

+ }

+ }

+}

+

+pub fn dijkstra<N: Debug + Eq + Hash + Copy + Ord>(

+ mut graph: LMap<N, Vec<(N, u32)>, impl Fn(N) -> Option<Vec<(N, u32)>>>,

+ start: N,

+ end: impl Fn(N) -> bool,

+) -> u32 {

+ let mut q = BinaryHeap::new();

+ let mut s = HashSet::new();

+ q.push(Reverse((0, start)));

+ while let Some(Reverse((c, n))) = q.pop() {

+ if end(n) {

+ return c;

+ }

+ if !s.insert(n) {

+ continue;

+ }

+ for (n, d) in graph.get(n).α() {

+ if s.contains(n) {

+ continue;

+ }

+ q.push(Reverse((c + *d, *n)));

+ }

+ }

+ dang!()

+}

+impl std::ops::Add<(i16, i16)> for Dir {

+ type Output = (i16, i16);

+ fn add(self, (x, y): (i16, i16)) -> Self::Output {

+ match self {

+ Dir::N => (x, y - 1),

+ Dir::E => (x + 1, y),

+ Dir::S => (x, y + 1),

+ Dir::W => (x - 1, y),

+ }

+ }

+}

+

+impl std::ops::Add<(u8, u8)> for Dir {

+ type Output = Option<(u8, u8)>;

+

+ fn add(self, (x, y): (u8, u8)) -> Self::Output {

+ match self {

+ Dir::N => Some((x, y.checked_sub(1)?)),

+ Dir::E => Some((x + 1, y)),

+ Dir::S => Some((x, y + 1)),

+ Dir::W => Some((x.checked_sub(1)?, y)),

+ }

+ }

+}

+