Розв’язок

Горизонтальні та вертикальні переміщення можна розглядати незалежно.

Спочатку розглянемо одну вісь із $d$ клітинок. Нехай q_0=0, а q_i — сумарне зміщення після перших $i$ команд уздовж цієї осі без урахування меж. Відстань між крайніми краплями після виконання команд дорівнює \max(0, d-1-(\max q_i-\min q_i)). Отже, всі краплі матимуть одну координату тоді й лише тоді, коли розмах префіксних зміщень не менший за d-1.

Це можна побачити, простеживши за двома краплями, що спочатку були на протилежних краях. Їхній порядок не змінюється, а відстань не збільшується. Доки вони не злилися, кожне збільшення розмаху префіксних зміщень на одиницю зменшує відстань між ними на одиницю. Коли крайні краплі злилися, усі інші також мають ту саму координату.

Нехай x_i та y_i — горизонтальне й вертикальне зміщення після перших $i$ команд, причому x_0=y_0=0. Команди L і R змінюють $x$ на $-1$ та $1$, а U і D змінюють $y$ на $-1$ та $1$.

Вікно префіксів із позицій від $l$ до $r$ відповідає фрагменту команд із позицій від l+1 до $r$. Його довжина дорівнює r-l. Цей фрагмент збирає всі краплі в одну клітинку тоді й лише тоді, коли:

• \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.

Знайдемо найкоротше таке вікно методом двох вказівників. Для підтримки мінімумів і максимумів використаємо чотири монотонні черги. У них зберігатимемо індекси префіксів.

Починаємо з префіксу з індексом $0$. Послідовно додаємо префікси з індексами r=1, 2, \ldots, m. Поки обидві нерівності виконуються, оновлюємо відповідь значенням r-l, видаляємо з черг індекс $l$, якщо він стоїть на початку, і збільшуємо $l$.

Якщо жодне вікно не підійшло, виводимо $-1$.

Доведення правильності

Умова для однієї осі є необхідною та достатньою для злиття всіх крапель за цією координатою. Оскільки рухи вздовж двох осей незалежні, одночасне виконання двох нерівностей рівносильне збиранню всіх крапель в одній клітинці.

Додавання префіксу до вікна не зменшує розмах жодної координати. Тому для фіксованої лівої межі всі праві межі після першої придатної також придатні й дають не коротші фрагменти. Алгоритм пересуває ліву межу лише після перевірки придатного вікна. Отже, він розглядає найкоротший придатний фрагмент для кожної лівої межі, для якої такий фрагмент існує, та знаходить загальний мінімум.

Складність

Кожен індекс додається до кожної черги та видаляється з неї не більше одного разу. Часова складність — $O(m)$, додаткова пам’ять — $O(m)$.