поиск | C++ для приматов

Задача

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

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

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

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

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

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

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

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

Решение

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

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

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

Код на С++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int LX; // абсцисса источника энергии
    int LY; // ордината источника энергии
    int TX; // абсцисса Тора
    int TY; // ордината Тора
    cin >> LX >> LY >> TX >> TY;

    while (1) {
        int E;
        cin >> E;
        string hor;     // Куда нужно двигаться Тору по оси абсцисс
        string ver;     // Куда нужно двигаться Тору по оси ординат
        // Определяем, куда нужно двигаться Тору по оси Х
        if (TX == LX)           // Если абсцисса Тора совпадает с абсциссой источника,
            hor = "";		// её менять не нужно
        else {				
            if (TX < LX) {	// Если абсцисса Тора МЕНЬШЕ абсциссы источника,
                hor = "E";	// УВЕЛИЧИМ её, т.е. двинемся на ВОСТОК
                TX++;		// Фиксируем изменение положения Тора
            }
            else {		// Если абсцисса Тора БОЛЬШЕ абсциссы источника, 
                hor = "W";	// УМЕНЬШИМ её, т.е. двинемся на ЗАПАД
                TX--;		// Фиксируем изменение положения Тора
            }
        }
        // Определяем, куда нужно двигаться Тору по оси Y
        if (TY == LY)		// Если ордината Тора совпадает с ординатой источника,
            ver = "";           // её менять не нужно
        else {
            if (TY < LY) {	// Если ордината Тора меньше ординаты источника,
                ver = "S";	// УВЕЛИЧИМ её, т.е. двинемся на ЮГ
                TY++;		// Фиксируем изменение положения Тора 
            }
            else {		// Если ордината Тора больше ординаты источника,
                ver = "N";	// УМЕНЬШИМ её, т.е. двинемся на СЕВЕР
                TY--;		// Фиксируем изменение положения Тора
            }
        }     
        cout << ver + hor << endl; // Склеиваем наши строки-"сдвиги" и выводим окончательный сдвиг
    }
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

int LX; // абсцисса источника энергии

int LY; // ордината источника энергии

int TX; // абсцисса Тора

int TY; // ордината Тора

cin >> LX >> LY >> TX >> TY;

while (1) {

int E;

cin >> E;

string hor; // Куда нужно двигаться Тору по оси абсцисс

string ver; // Куда нужно двигаться Тору по оси ординат

// Определяем, куда нужно двигаться Тору по оси Х

if (TX == LX) // Если абсцисса Тора совпадает с абсциссой источника,

hor = ""; // её менять не нужно

else {

if (TX < LX) { // Если абсцисса Тора МЕНЬШЕ абсциссы источника,

hor = "E"; // УВЕЛИЧИМ её, т.е. двинемся на ВОСТОК

TX++; // Фиксируем изменение положения Тора

}

else { // Если абсцисса Тора БОЛЬШЕ абсциссы источника,

hor = "W"; // УМЕНЬШИМ её, т.е. двинемся на ЗАПАД

TX--; // Фиксируем изменение положения Тора

}

// Определяем, куда нужно двигаться Тору по оси Y

if (TY == LY) // Если ордината Тора совпадает с ординатой источника,

ver = ""; // её менять не нужно

else {

if (TY < LY) { // Если ордината Тора меньше ординаты источника,

ver = "S"; // УВЕЛИЧИМ её, т.е. двинемся на ЮГ

TY++; // Фиксируем изменение положения Тора

}

else { // Если ордината Тора больше ординаты источника,

ver = "N"; // УМЕНЬШИМ её, т.е. двинемся на СЕВЕР

TY--; // Фиксируем изменение положения Тора

}

cout << ver + hor << endl; // Склеиваем наши строки-"сдвиги" и выводим окончательный сдвиг

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int LX = in.nextInt(), LY = in.nextInt();
		int TX = in.nextInt(), TY = in.nextInt();
		while (true) {
			int E = in.nextInt();
			String hor, ver;
			if (TX == LX)
				hor = "";
			else {
				if (TX < LX) {
					hor = "E";
					TX++;
				}
				else {
					hor = "W";
					TX--;
				}
			}
			if (TY == LY)
				ver = "";
			else {
				if (TY < LY) {
					ver = "S";
					TY++;
				}
				else {
					ver = "N";
					TY--;
				}
			}
			System.out.println(ver + hor);
		}
	}
}