Cheapest Path in a Grid
mediumGraphs II+20 XPTime limit 2s
A hiker crosses a rectangular park from the top-left cell to the bottom-right cell. Each cell has a difficulty 1 … 9, and entering a cell costs its difficulty (the start cell counts too). The hiker may move up, down, left or right — going back up or left is allowed when it avoids hard terrain. Find the minimum total cost.
Input:
- line 1:
r c - next
rlines:cdigits each (no spaces)
Output: the minimum total cost of a route, including both the start and the end cell.
Constraints: 1 ≤ r, c ≤ 300.
Think about it: because the route can turn back, a simple "right/down" DP is wrong. Cells are nodes and entering a cell costs its value — all costs positive — so run Dijkstra from the start with a min-heap: O(r·c·log(r·c)).
Sample input 1
3 3 131 151 421
Sample output 1
7
Sample input 2
3 4 1999 1111 9991
Sample output 2
6
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).