UniLecs #Task. Chess Bishop

Published in

UniLecs

3 min readApr 13, 2020

Задача: шахматный слон — это фигура, которая ходит по диагонали, причем только по одному цвету. Даны две клетки на шахматной доске. Необходимо определить, может ли слон достичь вторую клетку из первой.

Примечание: считаем, что на доске нет других фигур, кроме слона.

Входные данные: start = { ‘[A — H]’, ‘[1–8]’ }, end = { ‘[A — H]’, ‘[1–8]’ }

Вывод: кол-во ходов, ктр нужно сделать, чтобы переместить слона; путь слона. Если переместить слона не получается, вывести сообщение об ошибке. Если существует несколько решений, вывести самое короткое.

Примеры:

start = E1, end = E2. Output: Not found
start = A1, end = A1. Output: 0 ходов: A1
start = A2, end = F7. Output: 1 ход: A2 — F7
start = D1, end = C8. Output: 2 хода: D1 — G4 — C8

Разбор

На входе имеем: (Sx, Sy) — начальное поле слона, (Ex, Ey) — конечное поле слона. Рассмотрим возможные решения:

Start == End, тогда слона перемещать не нужно.
Слона переместить невозможно, в случае, если поля имеют разный цвет. Это можно описать формулой: Sx + Sy + Ex + Ey — сумма нечетная. (Буквенный координаты превращаем в численное представление).
Start и End находятся на одной диагонали. Т.е. Abs(Sx — Ex) == Abs(Sy — Ey). В этом случае слону нужно сделать всего 1 ход.
Необходимо сделать 2 хода. Очевидно, что если слона можно переместить из одного поля в другое, то это всегда можно сделать не более чем за 2 хода.

Рассмотрим случай, когда необходимо сделать 2 хода:
То есть для начала нужно сделать ход из (Sx, Sy) в (Mx, My), а затем из (Mx, My) в (Ex, Ey).
Очевидно, что поля (Sx, Sy), (Mx, My), а также (Mx, My), (Ex, Ey) будут находиться на одной диагонали. Отсюда получаем два уравнения:
Abs(Sx — Mx) == Abs(Sy — My)
Abs(Mx — Ex) == Abs(My — Ey)

Раскрываем модуль и получаем две системы уравнений:
Sx — Mx = Sy — My
Mx — Ex = Ey — My
и
Sx — Mx = My — Sy
Mx — Ex = My — Ey

Получаем: