Ragnarök — Power of Thor

 Рагнарёк

Задача

Есть Тор. А у Тора был источник силы. Больше нет. Тор движется по прямоугольному полю и ему известны его координаты и координаты источника. Наша задача: за наименьшее количество ходов привести Тора к источнику. Допустимые варианты движения приведены на картинке ниже:

Рагнарёк-2

Инициализация

Одна строка, в которой даны четыре целых числа:  LX, LY, TX, TY — соответственно абсцисса и ордината источника, абсцисса и ордината начального положения Тора.

Инициализация

Одна строка, в которой даны четыре целых числа:  LX, LY, TX, TY — соответственно абсцисса и ордината источника, абсцисса и ордината начального положения Тора.

Входные данные для одного игрового хода

Уровень энергии Тора. Нам он не понадобится.

Выходные данные для одного игрового хода

Одна из следующих строк: «N», «NE», «E», «SE», «S», «SW», «W», «NW», указывающая в каком направлении Тору нужно переместиться.

Решение

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

Во-первых, нужно учесть, что ордината растёт в южном, а не в северном направлении, как обычно:

 Рагнарёк-3

Во-вторых, если бы поле не было прямоугольным (или на нём были бы преграды, не позволяющие двигаться в том или ином направлении), то наш метод пришлось бы серьёзно модифицировать.

 

Код на С++

Код на Java

 

Related Images:

One thought on “Ragnarök — Power of Thor

Добавить комментарий