Конфета в лабиринте

Заметим, что если можно пронести леденец длины $$$k$$$, то можно и всех меньших длин. Поэтому сделаем бинарный поиск по ответу. Что бы проверить, можно ли пронести леденец длины $$$k$$$, сделаем обход в глубину, где вершинами будут пары из самой верхней левой клетки леденца и направления, которому параллелен леденец. Из каждого такого состояния есть $$$6$$$ переходов — два, в направлении сдвига на одну клетку вдоль леденца, и еще повороты на $$$90^\circ$$$ вокруг одного из концов. Что бы проверить, что мы не заходим на стену, можно предподсчитать префиксные суммы по каждой строке и столбцу. Итого решение за $$$O(n \cdot m \cdot \log(\min(n, m)))$$$.