Лорел Крик "— речка, делящая кампус университета Ватерлоо на две части. В речке обитают такие опасные создания, как гуси и бобры. В этой задаче вам придется найти способ переправиться через речку, не промокнув.

Чтобы этого добиться, требуется использовать пни, торчащие в некоторых местах из воды. На пне можно спокойно стоять, не боясь промокнуть. Чтобы перебраться с одного пня на другой, можно использовать брёвна, соединяющие их.

Но даже если добраться по брёвнам до конечной точки невозможно, ещё не все потеряно. Вы можете подобрать любое бревно, примыкающее к пню, на котором вы находитесь, и положить его в каком-то другом месте, так чтобы оно вело к какому-то другому пню. Чтобы можно было взять бревно (равно как и чтобы двигаться по нему), оно должно быть правильно ориентировано, например в конфигурации « S-S » бревно примыкает к двум пням, а в конфигурации « S|S » "— нет.

Для простоты, река размечена квадратной сеткой. Каждый пень находится в какой-то клетке этой сетки. Два пня помечены как начальный и конечный. Два пня, находящиеся в одной строке или столбце, могут быть соединены бревном. В каждый момент времени можно сделать один из следующих ходов:

• Пройти по бревну, которое примыкает к пню, на котором вы находитесь, до другого конца этого бревна, до пня, примыкающего к другому концу этого бревна.
• Подобрать бревно, примыкающее к пню, на котором вы находитесь. Более одного бревна в каждый момент времени нести нельзя.
• Положить бревно, которое у вас в руках так, чтобы оно соединило пень, на котором вы находитесь, с каким-то другим пнём. Бревно должно быть точно той длины, которая требуется, чтобы соединить эти пни. Бревно должно полностью находиться в воде, нельзя соединять два пня бревном, если посередине находится третий пень, или если уложенное бревно пересечётся с каким-то другим бревном, уже находящимся в воде.