1662. A Robot That Has to Recharge

A warehouse floor is a grid of r rows and c columns. Each square is one of:

# a rack, which cannot be entered 1 .. 9 a floor square; entering it takes that many seconds C a charging pad; entering it takes 1 second and fills the battery

A robot starts on the top-left square with a FULL battery of cap units. Entering any square, charging pad included, costs one unit of battery, and the robot cannot move with an empty battery. Entering a charging pad refills the battery to cap immediately on arrival.

Print the least total seconds to reach the bottom-right square, or -1 if it cannot be reached.

1 1 1 1 # 1 cap 4 -> 4 four squares entered, four units of battery 1 1 1

With cap 3 the same floor answers -1: the shortest route enters four squares and the battery runs out on the last one.

## The four things that have to be said

directed? no. Every move works both ways. self-loops? there are none: a move always changes square. parallel edges? there are none: two neighbouring squares are joined once in each direction. unreachable? yes, in three ways. An endpoint may be a rack, the racks may seal the target off, or the battery may be too small for any surviving route. Print -1 for all three. A 1 by 1 floor that is not a rack answers 0, with the battery untouched.

## What most people try first

Dijkstra on the squares, minimising seconds, and checking the battery at the end. The check cannot be made at the end: the battery is spent along the way, so whether a route is even legal depends on where its charging pads fall. A route that is fastest in seconds may be impossible, and the search has already discarded the legal ones.

The second instinct is to minimise battery use instead and hope the seconds come out well. They do not: a charging pad costs 1 second, so a detour to one is cheap in time and expensive in distance, and the two objectives genuinely disagree.

## The node of the search is a pair

Search the PRODUCT graph whose vertices are pairs (square, battery left), with the second coordinate running from 0 to cap. Its size is r * c * (cap + 1), which at the limits is 60 * 60 * 31 = 111600 states.

from (square s, battery b) with b >= 1, for each neighbour t that is not a rack: new battery = cap if t is a charging pad = b - 1 otherwise arc cost = 1 if t is a charging pad = the digit on t otherwise start (top-left, cap) answer the smallest distance over all states (bottom-right, b)

Note the asymmetry worth getting right: entering a pad spends a unit of battery and then refills, so the condition to move is still b >= 1. Every arc cost is positive, so Dijkstra is correct on the product graph as it stands.

## Why the battery cannot be checked afterwards, stated precisely

Minimising seconds and surviving the journey are different objectives, and neither bounds the other. Two arrivals at the same square, one fast with an almost flat battery and one slow with a full one, are both worth keeping: the first wins if the target is near, the second if a long stretch without a pad comes next. A search with one slot per square keeps the fast one and reports either a wrong number or a spurious -1.

The product graph fixes that by refusing to compare them at all. They are different vertices.

## Cost

O(r * c * cap * log(r * c * cap)) time and O(r * c * cap) memory, about 10^6 heap operations at the limits. The answer is at most the number of states times the largest square cost, roughly 10^6 seconds, so a 32 bit integer is ample.

Constraints - `1 ≤ r ≤ 60` - `1 ≤ c ≤ 60` - `1 ≤ cap ≤ 30` - Every character is `#`, `C`, or a digit from `1` to `9`.