A small autonomous drone irrigates a rectangular field that has been divided into an R-row by C-column grid of plots. Some plots are boulders the drone can never fly over; the rest are open ground. Exactly one open plot is the drone's launch pad, and exactly k of the remaining open plots are thirsty crop plots that must each be visited at least once. In a single move, the drone flies from its current plot to an open plot sharing an edge with it — north, south, east, or west; diagonal moves are not allowed, and it may never land on a boulder. Starting from the launch pad, find the minimum number of moves needed so the drone has visited every crop plot at least once. Revisiting a crop plot, or the launch pad, is allowed and free of extra cost, and the drone does not need to return to the launch pad once it finishes. If some crop plot can never be reached from the launch pad, report -1 instead.
A single integer: the minimum number of moves needed to visit every crop plot at least once, or -1 if that is impossible.
Example 1
Input
3 3 2 D.1 ... 2.#
Expected
6
Explanation
Both crop plots are 2 moves from the launch pad along the grid's outer edges (D to plot 1 goes right, right; D to plot 2 goes down, down). Whichever plot the drone visits first, reaching the other one afterward takes 4 more moves diagonally across the open interior of the field (the single boulder in the bottom-right corner never lies on a shortest path), giving 2 + 4 = 6 moves in total either way.
Example 2
Input
2 2 1 D# #1
Expected
-1
Explanation
The launch pad's only two grid-neighbors are both boulders, so the drone cannot leave the pad at all. The single crop plot is therefore unreachable, and the answer is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →