Solution

Horizontal and vertical movements can be considered independently.

First consider one axis with $d$ cells. Let q_0=0, and let q_i be the cumulative displacement after the first $i$ commands along this axis, ignoring the boundaries. After the commands, the distance between the extreme drops is \max(0, d-1-(\max q_i-\min q_i)). Therefore, all drops share one coordinate if and only if the range of prefix displacements is at least d-1.

To see this, follow the two drops initially at opposite ends. Their order does not change, and their distance never increases. Until they merge, each increase of one in the range of prefix displacements decreases their distance by one. Once the extreme drops merge, all other drops also share that coordinate.

Let x_i and y_i be the horizontal and vertical displacements after the first $i$ commands, with x_0=y_0=0. Commands L and R change $x$ by $-1$ and $1$, while U and D change $y$ by $-1$ and $1$.

A window of prefixes from position $l$ through $r$ corresponds to the command substring from l+1 through $r$. Its length is r-l. This substring gathers all drops in one cell if and only if:

• \max(x_l, \ldots, x_r)-\min(x_l, \ldots, x_r) \ge w-1;

• \max(y_l, \ldots, y_r)-\min(y_l, \ldots, y_r) \ge h-1.

Find the shortest such window using two pointers. Maintain the minima and maxima with four monotonic deques storing prefix indices.

Start with prefix index $0$. Add prefix indices r=1, 2, \ldots, m in order. While both inequalities hold, update the answer with r-l, remove index $l$ from the front of any deque where it appears, and increase $l$.

If no window satisfies the conditions, print $-1$.

Correctness proof

The condition for one axis is necessary and sufficient for all drops to merge along that coordinate. Since movements along the two axes are independent, satisfying both inequalities is equivalent to gathering all drops in one cell.

Adding a prefix to a window cannot decrease either coordinate range. Thus, for a fixed left endpoint, every right endpoint after the first valid one is also valid and produces a substring no shorter. The algorithm advances the left endpoint only after checking a valid window. Consequently, it considers the shortest valid substring for each left endpoint for which one exists and finds the overall minimum.

Complexity

Each index is added to and removed from each deque at most once. The time complexity is $O(m)$ and the extra space is $O(m)$.