A strategy game's map is a grid of strings of digits "1" to "9": each digit is the cost of entering that cell. A unit starts in the top-left cell (its cost isn't paid) and must reach the bottom-right cell, moving up, down, left, or right. The total cost of a route is the sum of the costs of every cell it enters.
Write cheapestCrossing(map) that returns the smallest total cost. Use A* search: every cell costs at least 1, so the Manhattan distance to the goal never overestimates the cost left and is a safe guess.
Input: map = ["1999","1111","9991"] Output: 5
Go down, right three times, then down: five cells, each costing 1.
Input: map = ["5"] Output: 0
The unit already stands on the goal and pays nothing for the start cell.
1 <= map.length, map[i].length <= 100"1" to "9".Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #469 Cheapest Crossing of a Cost Map. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.