Back
Close
EVENTS
UPCOMINGPASTPRIVATE EVENTS
AI GAMES
BOT PROGRAMMINGOPTIMIZATIONCODE GOLF
ARCADE
PUZZLESCLASH OF CODECODING ESCAPE
COMMUNITY
LEADERBOARDSCONTRIBUTIONSDISCORDFORUMLIVE STREAMS

Grid climbing

Statement

 Goal

You are given an integer n, an array costs of n-1 integers and a n times n grid of digits. You start at (0, 0) with a starting cost equal to grid(0, 0) and you want to reach the bottom right (n-1, n-1) with minimal cost.

At any turn you can move from (i, j) to (i', j') (different of (i, j)) with a cost equal to the sum of:

(1) the value of the grid at (i', j'), grid(i', j')
(2) the integer at the (d-1)-th index in costs table, where d = max(abs(i-i'), abs(j-j')).

Find the minimum cost.

Example:
3
1 5
132     X..
053  -> X..
011     .XX

starting cost = grid(0, 0) = 1
(0, 0) -> (1, 0) = costs[1-1] + grid(1, 0) = 1 + 0 = 1
(1, 0) -> (2, 1) = costs[1-1] + grid(2, 1) = 1 + 1 = 2
(2, 1) -> (2, 2) = costs[1-1] + grid(2, 2) = 1 + 1 = 2
total = 1 + 1 + 2 + 2 = 6
Input
Line 1: An integer n for the number of points to compare.
Line 2: A space separated string costs with n-1 elements, representing the cost of the distance.
Next n lines: The rows of the n times n grid
Output
Line 1: An integer for the minimum cost required to reach the target.
Constraints
In costs, the n-1 integers satisfy: 0 < c_1 < c_2 < ... < c_(n-1)
3 <= n <= 40
Example
Input
3
1 5
132
053
011
Output
6
Tags
Pathfinding, Dijkstra, Memoization, Recursion, Dynamic programming
Difficulty
Hard
Test cases
1. N = 3 (Example) Test
Input
3 1 5 132 053 011
Output
6
1. Val. N = 3 (Example) Validator
Input
3 1 5 132 053 031
Output
7
2. N = 4 (Special) Test
Input
4 2 3 10 0099 9990 9999 0000
Output
8
2. Val. N = 4 (Special) Validator
Input
4 1 3 8 0009 2993 9999 0000
Output
7
3. N = 5 (Special) Test
Input
5 1 3 7 8 00009 99990 90009 09999 90000
Output
6
3. Val. N = 5 (Special) Validator
Input
5 1 4 5 10 00009 99990 90909 99999 90000
Output
9
4. N = 5 (Special bis) Test
Input
5 1 20 21 22 00009 99990 90009 09999 90000
Output
12
4. Val. N = 5 (Special bis) Validator
Input
5 1 20 21 22 00009 99990 90079 99999 90000
Output
22
5. You actually can go back Test
Input
6 1 20 21 22 23 000009 999990 990090 909909 990999 999000
Output
14
5. Val. You actually can go back Validator
Input
6 1 20 21 22 23 099009 090990 099090 909090 990990 999990
Output
14
6. N = 6 Test
Input
6 2 6 10 14 18 622474 008140 242202 206800 111023 060400
Output
22
6. Val. N = 6 Validator
Input
6 2 6 10 14 18 035600 642220 532205 512311 412401 550513
Output
19
7. N = 7 Test
Input
7 2 6 11 15 19 23 2310005 3037470 4042735 5066450 2403174 1310240 0030501
Output
21
7. Val. N = 7 Validator
Input
7 2 7 11 15 19 24 0000240 0762020 0622865 0445300 5104861 5042140 0405000
Output
21
8. N = 8 Test
Input
8 2 7 11 16 21 25 30 06006131 50004030 06135764 03025100 10628045 04704532 51536020 02440050
Output
24
8. Val. N = 8 Validator
Input
8 2 7 12 16 20 24 29 02100445 30005741 03700430 46732422 60821360 05236100 06003232 20000100
Output
23
9. N = 9 Test
Input
9 2 6 11 16 21 25 29 33 005300005 550046360 420107223 344803050 045081020 204067030 003142603 200441332 050001000
Output
22
9. Val. N = 9 Validator
Input
9 2 6 10 15 20 24 29 33 555041000 150503000 000205001 100501410 130744000 032206630 060074014 015032123 005000323
Output
33
10. N = 10 Test
Input
10 2 7 12 17 22 26 30 35 39 0401050000 4030013050 1027053520 2060020130 0570385400 3007373010 0231152534 5000005101 5550500003 0010204003
Output
30
10. Val. N = 10 Validator
Input
10 2 7 11 15 20 24 28 32 36 3120002404 2016221101 0052031500 2304270004 5445334430 1601150002 3002010401 0006305300 0300030040 0340030222
Output
33
11. N = 15 Test
Input
15 2 7 12 17 22 26 30 35 40 44 49 53 58 62 660610625100200 032406110420354 306610566602102 042000103402610 057403873242000 007514768254010 510188052387314 363331447883220 006717915145015 042225685731545 621211300806505 651127600200103 013517520056400 022026263002300 261042160030502
Output
55
11. N = 15 val Validator
Input
15 2 6 11 16 20 25 30 35 39 44 48 52 57 62 156220300022010 300050100311404 460004400515030 107367030000500 422054286160300 516148100012711 020358766006500 044706740443026 000425460735403 206415167470202 134754236087154 001705113310060 214417470606705 424014030001525 420306240002263
Output
50
12. N = 20, no obstacles Test
Input
20 2 6 10 15 20 25 29 34 39 44 48 52 57 61 65 70 74 79 83 00002000500000010000 50050520335020411042 13062400056205202431 00304103605333103520 11401522365156256410 02640620217420003004 05000147075807720540 04004650820655516230 01637348107263300000 00003010557160000000 40261286645347613142 00645061512352260000 00413002083860012002 00007000231050440141 25200705023334004252 23141040256200031050 04340050061334110023 02000245003130450021 05252422140042502002 00210001340000300030
Output
54
12. N = 20, no obstacles val Validator
Input
20 2 6 11 16 21 25 30 34 39 43 47 52 57 62 66 70 74 78 83 52000300010004040003 05020431120322000032 00005000003100630100 02365500336522010050 03401304107510045033 34110436036366350110 00047102325725704020 03507025837706003504 32401036673404200000 50202048919120730020 30206613532001101010 22562705270083060004 00000708760840016004 45456364440205602504 50001011604404524501 05002201000000306511 10630154140100000032 00201000430440030012 04520010300200201100 00000300240000000000
Output
62
13. N = 20, obstacles Test
Input
20 2 7 11 15 19 23 28 33 37 42 46 50 55 59 63 67 71 76 80 12004001000050005100 20500044042000004400 00040499999999061300 04054699999999641030 00032299999999001100 40017499999999005501 01013499999999740000 01000699999999742003 13656399999999331500 02620099999999662120 45002700949122100300 20000334214856530054 00116388436606404531 20545130215076004420 54304320035266210100 40026300351142013200 00511422516204020510 30101010020220341123 00003101010400111123 23004102030033000304
Output
66
13. N = 20, obstacles val Validator
Input
20 2 7 12 16 20 25 29 34 38 43 48 53 57 62 66 70 74 78 82 04040000020501003000 14000020453002001020 53006506515030004000 30200001301150005521 00306203664017400099 00130255405253450099 45066160742800423199 35007032815563042099 00100217463067005099 50031001197604104099 41000521344330105313 00002567481240405002 03363727025855521500 00260014074700030010 13301302603600341103 00342010530030344500 00560265563261215400 20205012005200440020 02045999999040001054 01344999999103100340
Output
61
14. N = 30 Test
Input
30 2 6 11 15 19 24 29 34 38 43 47 52 57 61 66 71 76 80 85 89 93 98 102 107 111 115 119 124 128 000000000101020002000000001001 003100010000100000000012000220 200200203020001100032020002000 103300300000142400400031223011 101003003232000040300000201101 011002054122200400340001400000 010030502011020444000220001010 000000020400402533031203300002 022420555624056036210030000000 103120040600042710052303010020 000000103460100722170640000000 201042000233604483234505000020 013025105355707047600403000002 000031054073273450161050400010 003343020226866452703542020001 002002405313872837405035002320 020200440240501060770210000000 100205526050700627060050030000 032010000240330107000233040000 230301215100600160553000420220 103015203220035060620305320000 000014432005034602630300000000 001001420005000052500303100100 100035002002305001000103420310 100000010410003101004140202021 000231000001041004013000300002 010000133210330000001000100000 021003002002030003000000000002 000000020000000000000200021100 202000020000001200000000000000
Output
78
14. N = 30 val Validator
Input
30 2 7 12 16 21 26 31 36 40 45 50 54 59 63 68 73 77 81 86 91 96 100 104 109 113 117 121 125 129 010200200220020000101000000210 000000100000023000320330003020 100000000003000000201300000000 113002004000032210300020041001 000000230102003000003000000010 001002030002300010100000000000 010025020502410000005540040200 000340000560232064000505000000 000034000030640340020133000021 010001440300714667473000000110 000000406262200060723033330100 100300265307303328313420420000 000203014022882862210020000001 010042046524079175003210000022 001020065223883361150522002100 003001061702438156140300101000 200330020105623468314605103000 100030560425074626430055201002 000405243650324274660000001000 000000034776013501042010320001 000405024204526004116105002000 000022005314004000003030000000 001000200500050220152520200300 200300000331000003050540010000 000400000000203022020001330321 002000043020000000010100002002 210000002000200200000100101020 001000010000000032303030030000 000000000002001000010121000000 000200000020000000000000000000
Output
79
15. N = 40 Test
Input
40 2 6 10 15 19 23 27 32 37 41 44 47 50 53 57 60 64 67 70 73 75 77 80 83 85 88 90 92 95 97 99 101 102 103 105 106 107 109 110 0009000000909000000000000000000000000000 0009000000909000000000000000000000000000 0009000000919000000000000000010001000000 0009000000909000000000000010000100000000 0009020100909002000200002000000210000000 0019000010909200000000000000122000000000 0009001010909002000101020300200000000000 0009000000929001000102000110302001010000 0009000030909030010000020020000330201000 0009020203949004003200000234003000000000 0009002002909120004042000540002000000000 9999999999999999999999999999999999999999 0019200020909605462060006200010000000000 0009000320909660230130004013400002000000 0009000011909065300042075550300020000000 0009003003939010476232700013002110100000 0009001000919001173807307000230000000000 0009010300939175145817765000102000011000 0009010011909500146523857040000130000000 0009000001959045485030560202400000200000 0009000001949002501692020000540010000000 0009000021929650075277150230000110000000 0009010003919330550656346330041001200000 0009003003909031201510072004033000000000 0009002211919152561111050460000000000000 0009000000909402002404102000410000000000 0019103030919002034164510500000010000000 0009200000929120040253240400010000000000 0009000004909100025050020034033011000000 0009002100929020300004300012020001000000 0009000004919200440204140030010010000000 0019000201909300200020000023000000000000 0009010000909100000202010021003000000000 0009000000909010020000000200002000100000 0019000201909000100010201101000001010000 0009000000909001010000000000010000000000 0019000000909100000000000000000000010000 9999999999999999999999999999999999999999 0009000000909000000000000000000000000000 9999999999999999999999999999999999999999
Output
113
15. N = 40 val Validator
Input
40 2 7 12 17 21 26 30 34 39 43 47 51 54 57 61 65 68 72 76 80 82 84 87 89 91 93 96 99 102 105 107 108 110 111 113 115 117 119 121 0000000009999999900000000000090000000990 0000000009999999900000000000090000000990 0000100009999999900000000010090000000990 0010010009999999900000010000091000100990 9999999999999999999999999999999999999999 0010022109999999900001000002090002009999 0000002009999999902002300001090000009999 0000200009999999930300300000090030019999 0000202000001042201003040200492101209999 0000000004000411999999990132290330009999 0000000330000520999999990330094031009999 0001000300004000999999990400390020009999 0000000100000520999999995340090300009999 0001002001005343999999990053590002000990 0000000000001332999999997415090030101990 0000000021510070999999990521090000201990 9999999999999999999999999999999999999999 0000220003445272407876600060092020000990 0000000040104200523720462001090102001990 0000000240506212009690707460090010000990 0000000310253300228244601060590000000990 0000000033125336184730050520093212000990 0000200002500045708401163200490000110990 0001121300024501064500307002091100000990 0000212000056320730152501501090001000990 0000223002141640060006000544492000000990 0011003001540200621262000002090012000990 0010000003300002000000033000090000000990 0000000003000310300001530050190000000990 0010003000124241300102102040393002100990 0000100000004000000400003401090000000990 0000001300000012000120000100090000000990 0010000003030001000203030003290212010990 0000000020200002202000200001190000001990 0000020002000002000020020000090000000990 0000000100010000000000000000090000100990 9999999999999999999999999999999999999999 0000000000000000000000000000090000000990 0000000000000000000000000000090000000990 0000000000000000000000000000090000000990
Output
115
15. N = 40, the biggest jump Test
Input
40 2 7 12 16 20 24 28 33 36 40 43 46 50 53 56 60 63 66 69 72 74 77 80 83 85 87 88 90 91 93 95 97 98 99 100 101 101 101 102 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000001000000000000000000000010000 0000000000000000000010000000000000000000 0000220000012200002000000000000020000000 0000000002010012000020000220002200000000 0000010012233001100000030000230000000000 0000000102110000000302230000010302100000 0000000000000103000100000420003000000000 0000000243000400320010400100020000100000 0000003003434320400000002142400030100000 0000100000050130100340230452400300000000 0010020002134000460050200230000100000000 0000000000032110102462205300001030200000 0001000000200136371056710602504200010000 0010002114050202452001607000100300000000 0000010131342153732305604202500100000000 0000200000035270102168122030004200000000 0000100022005150764652660005040020210000 0000000312250470468967751060030010000000 0000012000453076270072006143432000000000 0001020020026260172056850030000200000000 0000000010046030354640037030010202000000 0000000003405012635656641301110300000000 0010000321000231274154102110001002000000 0000000022016252054310631000400100000000 0000001004313000011012012045000000010000 0000003302200251404000040241120000000000 0010223001000340055550022005300301100000 0000200000000030404020300303003030000000 0001001020410000000000011034200000200000 0000001000001000000001000001000030000000 0000000120112020001000000002200200000000 0000000000002020000000000000000200110000 0000100000000002000000000000010001200000 0001001100000000011000000000010001000000 0000000000100000000000000110000100110000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000
Output
102
15. N = 40, the biggest jump val Validator
Input
40 2 7 12 17 21 25 30 34 38 41 45 48 52 56 60 64 66 69 72 75 77 79 81 83 85 86 88 89 91 92 94 95 96 96 97 97 97 98 98 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0010000000000000000000000000000000000000 0000010000100000000100100000000000010000 0000100000002011001101000020000000000000 0000000020010200002120010100110010000000 0000000000310200000330010000000001200000 0011200010000200003000030100020000000000 0000000001003400424020424040340000100000 0000000040300200031044040100300001200000 0010003024053000020051002210404200001000 0000001034200103020140000030532000000000 0000020103331500033310010555030000010000 0010000230426063021022130221020301100000 0000002120306443440640740350030002000000 0000003200046143600560025400000000200000 0000100301024041853400405160304000000000 0000020000315526006743613100000000001000 0000000200010616083002667301422000000000 0000202002025051359322102000400000000000 0000000001130300675135871301014000000000 0000000141005566122888665630200220000000 0010000000303003145554152010212000000000 0000000000404041007577047202401000000000 0001020040340360007067047051110300000000 0000020000203031414655011013000000000000 0000000140500024460006204433044300000000 0000000220500051540000502200500100000000 0000010010000130422100500010003000000000 0000000040010302230110303030024100000000 0001000020433100000000300023024230000000 0001003030001000132300022000200000200000 0000000011002010000003000032000210100000 0000000002000010020000000000120000000000 0000100020000000200000020000200000000000 0000000000000000110000100000000000000000 0000000000000000000000010100000100000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000
Output
98
Solution language
Solution
Stub generator input
ABOUT USCAREERSPRIVACYFAQBLOG
ABOUT USCAREERSPRIVACYFAQBLOG

The #1 tech hiring platform

SCREENINGINTERVIEWING
FacebookYouTubeTwitterLinkedIn