Skills101
← All coding problems

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 r lines: c digits 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).

Loading editor…

Log in to run and submit your code — it's free.