Матч 348, Оптимальный список (OptimalList)

Дивизион 2, Уровень 1

У Билли имеются детальные инструкции как пройти к дому бабушки. Они представляют собой строку из символов ‘N’,‘S’,‘W’,‘E’, описывающих соответственно движение на один блок на север, юг, запад и восток. Двигаться можно только в горизонтальном или вертикальном направлении.

Билли необходимо составить новую карту маршрута к бабушке, состоящую из наименьшего количества инструкций. Если существует несколько оптимальных маршрутов, то вернуть алфавитно наименьший.

Класс: OptimalList

Метод: string optimize(string inst)

Ограничения: inst содержит от 1 до 50 символов ‘N’,‘S’,‘W’,‘E’.

Вход. Строка inst, описывающая путь к дому бабушки.

Выход. Количество возможных местоположений врага.

Пример входа

inst

“NENENNWWWWWS”

“NNEESSWW”

“NENENE”

Пример выхода

“NNNWWW”

“”

“EEENNN”

РЕШЕНИЕ

обработка строк

Промоделируем процесс движения к дому бабушки в декартовой системе координат. Начальное положение Билли положим равным (x, y) = (0, 0). После обработки списка инструкций inst точка (x, y) будет содержать координаты дома бабушки. Строим новый список инструкций в алфавитном порядке.

ПРОГРАММА

#include <cstdio>

#include <string>

using namespace std;

class OptimalList

{

public:

string optimize(string inst)

{

int x, y, i;

string res;

for(x = y = i = 0; i < inst.size(); i++)

if(inst[i] == 'S') y--; else

if(inst[i] == 'N') y++; else

if(inst[i] == 'W') x--; else

if(inst[i] == 'E') x++;

if (x > 0) res = res + string(x,'E');

if (y > 0) res = res + string(y,'N');

if (y < 0) res = res + string(-y,'S');

if (x < 0) res = res + string(-x,'W');

return res;

}

};