Перепиши на C++, может зайдет :)

Я толкал DFS-подобный перебор по состояниям вида (расположение ящиков, компонента связности, в которой стоим). После получения очень длинного ответа укорачивал его, проходя внутри компоненты кратчайшим путем и пытаясь "срезать" цепочку состояний. #TLE из-за первой части немного предсказуем.

У меня был бфсоподобный алгорим, типа A* (A-star), насколько я понял его из вики. бфс шёл вроде как с двух сторон, попеременно вынимая элементы из этих двух очередей, останавливаемся когда встречаем вершину достижимую с обоих сторон. Помимо этого была оценка на близость к ответу(как в A*) которая в идеале должна была вычисляться венгерским алгоритмом между ящиками и их позициями, но по факту какой-то жадиной для скорости. Кроме того использовались отсечения для тупиков. т.е. например если какой-то из ящиков загнан в угол не являющийся точкой назначения ящика, то бессмыслено сиськи мять и гонять оставшиеся ящики туда-сюда, ибо этот ящик так в углу и останется. Некоторое время у меня был АЦ, потом отсудили, потом опять АЦ, потом стало много житрожопых тестов и это не проходит снова и по видимому безповоротно. Имхо такую лажу более не впихнуть.
UPD: после ограничения размера графа поиска "с конца" до 2^13 вершин решение прошло до 57-го теста.

Когда-то, в марте 2008-го, я доходил до 56-го.

В январе 2012-го попробовал сдать еще раз. Аккуратно написанный bfs по состоянию "где сейчас ящики" дошел до 22-го теста. Далее я насчитал следующее: "предположить, что на поле нет ящиков, и для каждой клетки предподсчитать, куда можно из нее переместить ящик". Отсечение "проверять, что каждый ящик может дойти до конечной клетки, в которой сейчас нет ящика" доходит уже до 53-го теста. Если проверять, что существует паросочетание из ящиков и конечных клеток, то в системе это все равно падает на 53-м, но на моих тестах работает заметно лучше (раз в 100, 1000 быстрее). Далее планировал добавить meet-in-the-middle, но поленился.

UPD: не bfs, dfs с запоминанием