РОИ: Условия задач

Поле в Pinball представляет собой прямоугольник без стенок, состоящий из n x m квадратных клеток, (n клеток по вертикали, m клеток по горизонтали). Клетки по вертикали нумеруются сверху вниз, по горизонтали - слева направо. В каждой клетке можно установить одну отражающую пластинку в одном из двух положений: в положении 1 - от левого верхнего угла к правому нижнему или в положении 2 - от левого нижнего к правому верхнему. Летящий шарик при столкновении с пластинкой изменяет свою траекторию, при этом угол падения шарика всегда равен углу отражения и составляет 45° (см. рисунок).

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

Изначально на поле были расставлены k пластинок таким образом, чтобы шарик попал из точки A в точку B. После этого одну из пластинок удалили. Необходимо определить, куда и как можно поставить удаленную пластинку, чтобы шарик, выпущенный из точки A, попал в точку B. При этом требуется, чтобы длина пути шарика была минимальной. Пластинку нужно поставить на некоторую свободную клетку даже в том случае, если шарик попадает в точку B и без нее.

Требуется написать программу, устанавливающую пластинку таким образом, чтобы шарик попадал из точки A в точку B и длина его пути была минимальна.