Statistics

Problem Statement for "SlowTerrain"

Problem Statement

You are travelling across some uneven terrain in two dimensions. The map of the area in which you are travelling is divided into a 2D grid of cells. Each cell takes a certain amount of time to cross. (The time for a given cell is always the same and does not depend on the direction of travel.)

Your goal is to determine the fastest path from the given starting point to the given destination.


You are given a String[] terrain, where each character represents a single cell of the grid. Characters '0'..'9' represent the amount of time it takes to travel across the cell. 'S' is the starting point, and 'D' is the destination. (Leaving the starting point and entering the destination takes no time at all.)

You can only move horizontally and vertically. More precisely, your movement is a sequence of steps, and in each step you must move from your current cell into one of the cells that share a side with your current cell.

Return the shortest amount of time in which the destination can be reached.

Definition

Class:
SlowTerrain
Method:
fastestPath
Parameters:
String[]
Returns:
int
Method signature:
int fastestPath(String[] terrain)
(be sure your method is public)

Constraints

  • terrain will contain between 1 and 50 elements, inclusive.
  • Each element of terrain will contain between 1 and 50 characters, inclusive.
  • Each element of terrain will be the same length.
  • Each character in terrain will be '0'-'9', 'S', or 'D'.
  • Exactly one character in terrain will be 'S' and exactly one character will be 'D'.

Examples

  1. {"S32", "030", "41D"}

    Returns: 3

    The optimal path is to go down, right, right, down, 0 + 3 + 0 = 3.

  2. {"3D47S6"}

    Returns: 11

    Note that the start and destination don't have to be at the edges or corners.

  3. {"0S9", "09D", "000"}

    Returns: 0

    Sometimes a path with more steps and more changes of direction may be faster to traverse.

  4. {"0S9", "89D", "000"}

    Returns: 8

  5. {"1S9", "29D", "345"}

    Returns: 9

  6. {"352950474084209572403780174279215920155279747D4999","05869566278629576937841623404278427335536487754916","05621531460629092921313914549685872222110208391977","35793816079927858478798011146126712388430513109207","17189366817799532055790481849018480548286102535188","89750267S07427709209083869598855760220987868444421","60528040154289517665893211154250762404707183459732","67863662168969035270038587007624225720258821284920","97921292866655436433159122063920866549137925812678","10589378081298458889872061243003948159727683150413","33880475281340772492081512898008206651444978141854","26492522685771720441110581124700448433704346961508","36342059104979743323977378746195153369178426645485","28279690733129097263741444406222519124674627462357","63847767241944105199635990230721495941315411642764","10360378465274294482547832143584766187821566536786","07848624381359814170066609712954565153798349089784","85985312389113377946513717265290281947010309071063","10218721680470888323298262047451921971036211156901","88830110457842385599172869870160355626107664688882","90000060602493964866683914171819881503540200837350","39216171859887925113613163821878214177108849523215","75114151522400815727589157735395151161736528738314","66040850564151373596449919613294217356425650849050","02440270302463709440160607990605531697145534019128","44658327422796068311023946366978712580483239185734","26908217120614440745788378847516227186393182871946","87286386303795143863544516954069907334543233562214","42211437703212347887082203009447406478930575001001","93443590173282667068798575171910985020605771977494","30424058674281623975374539165986776067455438628557","47730568848826974055655209359015185193704790661698","88090924312098327417803418655376502251869405838073","97510745812789355860766483076705724004947926325022","89476201266791179652409128491670549010619912700146","39497702488106962410680325963172443855610868289431","85940480627382066530167007221454223130480484369376","14139189422692721688260407836379442039223361634670","53493546323530531596913649988621558345066660980663","28611307446686919821864303526583143344343605007917","82344643187708624335754881592956197597079035655197","63650385630511215110263556281253943106937417649125","94985990930043765670092838568170553140942065270799","82415011563218504805247280365587692563030252198802","21747451356469855260417750941915623602279405655535","36198140965193318362530809020043066536412935285724","61919953880199110268819406055233063239669985009331","82036524039086571369706988333966143136970992780103","86743860572910738423354898132971301087055201508854","96969319546275016097413680423803789126078826825413"}

    Returns: 115

  7. {"98328989663359699902958776591933498189708825257582","44668395423976309505092030334289194878141255791612","52431525280611337815213548373496127648895153441413","13469489922528935847890291501979692515328585708630","82944132678779538363105183055929611491502985318994","15008868511877590680367502108751507786228164942104","01180574966608602607143522036600036396020366520879","25122676674383565612055867779012574487105293775219","64658692558066527090784178520915603650974615156375","95201895800726334628660161690112450626956029773517","19098340492056873667186715314870720215661119365610","46936223739265112255670969673597044104579773784681","32053660776501322200187768971749821764084968137595","62570553856990267706572261196303751240161364140664","60539893193665522399265342171105217073522182356098","27772942976220873484497661730951829285976548608846","12143300011129253916885189499529947294852758553451","79687370548114812819580531365350388330645894716093","25255880450051877265811746968252710087294261453750","33335145188121073418990616492932078193686263029407","18670336287422561428898216365879957452758217120484","14119204630603174640087705800969817277654163421763","73983264133037618868970959232741361390845353238973","42084029239313917652170126177203693115211974522130","61341628588520266207014311956030375S99177929436771","95015947939672547154364438820054237439870108702949","54138205860279854340082731566268804038544701684102","68538623966485924747158062710574546834178998799514","47620094759023828491805691502632961072358865877595","04696310385921260628460320397240065869078794095532","60311442750130449553006597663347655379514324663805","09091647147893125850790497828337573477399971364823","15398096048298092107574608190339941746925179179903","32858417898956183572562824045382869013666779455082","33278709333624161870799068924680629491820192394287","47374442008756530946690506966736462179850707325370","85720477784752713933610959821706968791583920121702","96934748605569778949113596907381197465203155383223","32300834378402243613026369582136749671890225281228","56192150402522326536628128011783535757180767750919","25962379740386289966794459504681015248029507768058","50252314037750593609408461867804451785921987410928","310534288045713329971877842094194858491D6596985264","19104744269119395185483732117932667598911322244029","34309363625263365418961640604881876885649517687985","89940627597598343875808694440636180814795197736332","48237712562869503085291796109570082448127991674016","95589474406039817861559573091120926252877040575034","06301469164832860136649835190089561569016512296119","63778575653680842713910190375489713428767125896038"}

    Returns: 61

  8. {"94357710916397732394578530323778991917194721840939","53052257164871374957242908576904931483693354559170","90357100547812609499912649883483959903504D78224237","56518188718226053853795895129396508822130122772187","96690507230684116181207225720130424305028508342816","10274894748760901597001627089728149277754685309982","27835096478040295117247333252180964508882130731824","57810895918342971856973241175924286028566486087019","22264846686190940658532904861540567916386517945865","80534902690741466330342719150599967351179804891023","82562388247420908731041514388281377732434797946947","13612309570990661532653963536684400442536376357903","30521696487638955991190952776166232782944876500967","98991405688203113051739473133528082863186251627344","69349585182721501213498755878468899355869123590366","04119605947066248222554533752554124167922963994511","07140506868433928420713995906382405737181082475246","00203941455904850281913387204296593793663136219438","73427979266371593010665277870678665622230010904103","89332071591085976168608705552736678753349072202502","33416705265197643171237295264039504025007916971068","61889052214412366825281643202141963116144938637823","13805892457590624491407712520053790138042915690213","92918050933714047995954495920222061246195296147752","20263384121307117527907007673582689194384059712259","71472122567006396170122429482853247679588686030968","50458499436407038686176914453995243597536842146057","53096735339455311645400593337783963543751332322889","20603435934976565817688830672704584778392934115777","74603317627531294917965257437249050674515921176211","76608184558704784716294019340802264830797399288833","28059725887446555499540288048315065226776718239246","24838878706775713712397137220598010676874396089510","91112276005582086640468380001486095769888068294761","231062373227551859622776230918534924593348565150S6","34503946482236469353725538310108037492097810010210","58969089756352841089673658145271005283476944342825","90313843109345852575686136283152203689767523825957","17169041766599461422638070623112350805022610015281","11731781983186532495653900170543429959420961907556","91324678306003497665829656910926246201732764698279","21907626786673708661958231650576306162600349669266","12569727669661002665350606195724844507198950037386","32502619535319458174945674905797093987174118357655","55646868386138483264600908373263492316242943127335","25918446375951126360669117678709370143178424833218","63738557918786655810832912452833591720856639805673","75109217160041852949259642930068790715985581461203","86170255673771022500369647671817271979882692578712","35199274335747655991436187771699685552892255342159"}

    Returns: 102

  9. {"70801249273505219210927183451230160465154298173694","90770527177880334447440556290108662324551843854847","29110592142360792180098965077924428065674021272369","32037212444251188416264060766836086931558302214094","97296679775456081752479678628456629640191447937324","07570185170502188374305509316402044818178894863161","53680919708697685682791955116351458652357111919170","16344626257023461399323255800350362970124898778772","05287830887168976615902644345861383974935722432180","02523935325850268759916791801121657350546117862198","44680857210242932028172137099296036857487783337874","41916614538689142051755303987991258779606021019928","17356965027265363303633547243940698287891283243673","85881837096111875771864114403036601828708069S20075","48696511667334960410957063795813648276049751064662","25976905237158536857934601059081325549891147771766","95083913649461568329970668968302920214964133065221","98577253150443465312543557366036473271586724696993","02196449298871230691837267199513620155197895970113","90085648383496852411745049423870766138636712529264","55905449352144127307137740224101692106116341052613","55282182641252415520101817966985115497613806938169","97401543751157650370288073949787069100090501913203","35467184375949641884503796770507354333972672301045","94458216614137785843179128314846255528611677302944","52504153309028678711672314017153693211140946114916","25738702991351464244566706261091019062151821263215","72460589215408093324911927444330463673141699077413","30075515420449850453102822118590310396075298372015","62871271424068301385534789135501938615985717356052","58160380921469120296964097174320729293358056601250","43193941632166907499279478073968138997807860274876","26367647149776639270195914181041976955524253101939","71065303435651077007746569318021512213138102786424","31952355060953030498548795347829847129986525396714","72448921669172300169014020124096230044688023958922","84023574177076638313655800811622021450052028082665","74895292137625559552873605367272458831685296757735","8704700189925964266718966576848632301088722682700D","33005307372232313836621889853838765175782272654994","44334022265535334772380533482259593943149531378292","06270638005399159424915238491652991868865531955407","73043919322474533972906583743720848124626646418855","26677674691766925254083562501758874631613787090861","56315321150729329913845402054627391956203201065848","01623009123764333273626005443371166001609650755577","22001846276667416072226640663498651510585498430855","95844053501827789059055968382108085401019754772106","39264408766714028423879403011961867064304134425135","97968607504878058560530186350888860821719982654549"}

    Returns: 73

  10. {"95678125772500722775055853271048456514368420914382","65281308258546340532084176348389984955434228830574","09951811150508695513941077562458733893768348292318","75335689832487928658017555027752546043879954435790","16828578805610809418748890631193366933503558138564","41502680389476023548658052996511767872391206198988","03077825507837686081501473529649185800986173128203","27062916933058676517760043382443264694666405566964","63025560285335897940819503644874188129089927030575","86465445129153012467788509814721799195346688873968","16898089565203984649261200996359466627092096845590","37476446971822157472565562743654069757912683747653","61764629146923268523005509817141909364235565424510","62312662558029050138033985400852965177737486543649","12130283371617950538724005564317516306633330113179","37361981247290540906439053938923949349074941504346","S0310598207942213241101921597449692892999518370619","28022694889018673504203416936518771694659440084225","35676245066572612369899447524226101620091339936238","60626351396217404710822785695003856108470071292659","89039388317662833502952308515830462025533253944438","665292773177D3587200708979709353076264169352456895","12446787732173786972120303555128141395184877475146","87163910422225030314807883529273093564021818526170","72007793893811581224762829982664595530156350927036","03823091778002383259510783019029555353545124763370","94441921490727495469296034860207480741450496489497","08678984070611933477449198006544621106909007433761","44723695809874269808274684326553340074942589112658","44688700383692564331949657845716681064639600155544","69338940308546660104996022495013910232926615432334","54404623165553856364371883815800504789640012601868","78790735208072659481776133682729461126974265592861","07051016571434886014234075015407206599519602598277","32728729759000742373974946225768381899192919186041","75447578724049917198521800548602730149051129524109","14065535379291222097770374022754484510847863691173","94122437915125257166012409177828498021501416955000","10402716233691967371265645064441666244609582655063","81298447577528929247136726729900915287827689243034","52592554627286675027314295464726944749806306458125","82861383070808902329361209177463399983309091973163","24931206512065075090290293602369141130778171784312","22260347385042539148342211184182801364386669177563","92938700591622932411658517830336101625133694703398","53446444118691544103072780648135428017372839566782","51257707668950732725278212321248555128409407922321","38439839454754194945142258603899008541678239519660","72960962811366557556533778036389430704999125555730","44194481818254228358425663082233959484868857066822"}

    Returns: 44

  11. {"D1234","56789","0123S"}

    Returns: 11

  12. {"S11", "111", "999", "99D" }

    Returns: 12

  13. {"0S9", "09D", "000" }

    Returns: 0

  14. {"S32", "030", "41D" }

    Returns: 3

  15. {"S0", "50", "50", "50", "D0" }

    Returns: 0

  16. {"S99", "999", "99D" }

    Returns: 27

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: