Не могу найти ошибку в своей логике в поиске кратчайших расстояний от одной клетки до всех остальных в пределах одного шаблона в Div1-1000. Эта тема уже поднималась на форуме топкодера.

Задача стоит так: найти кратчайшие расстояния от заданной клетки (R,C) до всех остальных клеток (R',C'), находящихся в том же шаблоне, т.е. таких, для которых floor(R/H) = floor(R'/H). Один из способов заключается в том чтобы сделать лабиринт конечным, дописав к начальному шаблону еще X штук сверху и снизу, а затем искать кратчайшее расстояние обычным bfs'ом. 

Я думал что X<=W. В задаче с ограничениями из СРМа достаточно было взять X<=W+3 (подозреваю, что и X<=W тоже подходит), но в общем случае это не так. Существует тест 49х48 для которого X=61.

Вот мои рассуждения:

Предположим, что кратчайший путь из (R,C) в (R',C') спускается более чем на W полных шаблонов вниз (назовем это количество X_d). Выпишем все номера столбцов, в которых следуя этому пути мы пересекаем границу соседних двух шаблонов по направлению вниз (это касается только тех шаблонов, которые лежат не выше чем тот из которого мы стартовали). Так как X_d>W, какой-то столбец повторяется дважды. Вырежем весь путь между этими повторениями, уменьшив тем самым его длину. По предположению наш путь кратчайший, следовательно, укоротить мы его не можем, отсюда Xd<=W.

Аналогично покажем что максимальное количество полных шаблонов на которое нам нужно подняться вверх (назовем его X_u) не превышает W. Поскольку X=max{X_d,X_u}, можем записать что X<=W. 

Где-то в моих рассуждениях есть ошибка (раз существует контрпример), но я найти ее не могу. Буду благодарен, если кто-то укажет на нее.