Матч 16, Сломанный лифт (BrokenElevator)

В доме сломан лифт, и вам по ступенькам требуется добраться из одного места в другое. Массив строк plan содержит план дома. Четные строки массива plan описывают этажи, они содержат символы ‘#’. На этажах расположены буквы ‘S’ и ‘F’, обозначающие соответственно Ваше начальное и конечное положение. Нечетные строки массива plan описывают область между этажами. Символ ‘.’ обозначает пустое место, символ ‘|’ обозначает ступеньки. Каждая строка с нечетным номером содержит один символ ‘|’.

Вы тратите 1 секунду на передвижение на один эаж вниз, 3 секунды на подъем на один этаж вверх и две секунды на передвижение по этажу (влево или вправо) на одну позицию.

Требуется найти наименьшее время, за которое можно добраться из начального положения ‘S’ в конечное ‘F’.

Класс: BrokenElevator

Метод: int wayTime(vector<string> plan)

Ограничения: plan содержит от 1 до 49 строк, plan содержит нечетное количество строк, plan[i] содержит от 1 до 50 символов.

Вход. Массив строк plan описывает план дома.

Выход. Наименьшее время, за которое можно добраться из начального положения ‘S’ в конечное ‘F’.

Пример входа

plan

{"#S###","...|.","#####",".|...","####F"}

{"F", "|", "S"}

{"#F###","...|.","#####",".|...","####S"}

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

16

3

20

РЕШЕНИЕ

моделирование

Между каждыми соседними этажами существует лестница. Поэтому если начальное положение находится выше конечного, то мы никогда не будем двигаться вверх. Соответственно если начальное положение находится ниже конечного, то мы никогда не будем двигаться вниз. Всегда будет существовать единственный путь, ведущий из клетки ‘S’ в клетку ‘F’.

Находим координаты начального ‘S’ и конечного ‘F’ положения, занесем их соответственно в переменные (sx, sy) и (fx, fy). Если ‘S’ и ‘F’ находятся на одном этаже (sx = fx), то возвращаем значение 2 * (sy – fy).

Искомое время в пути будем вычислять как время, проведенное на ступеньках между этажами плюс время, проведенное на этажах. Если движение от ‘S’ к ‘F’ совершается вниз, то на каждый проход между этажами будет затрачиваться 1 секунда, иначе 3 секунды. Если ‘S’ находится ниже ‘F’, то для удобства поменяем их местами (путь от ‘S’ к ‘F’ совпадает с путем от ‘F’ к ‘S’). Далее будем считать время, затраченное на путь сверху от ‘S’ вниз к ‘F’. Заметим, что если ‘S’ находится в строке sx, а ‘F’ в строке fx, то между ‘S’ и ‘F’ находится |sx - fx| / 2 этажей.

К общему времени res прибавляем время, затраченное на движение от ‘S’ до ближайшей лестницы в строке sx + 1, ведущей вниз (оно равно 2* |plan[sx + 1].find('|') – sy|) и на движение от лестницы в строке fx – 1 до ‘F’ (оно равно 2* |plan[fx – 1].find('|') – fy|). Далее суммируем время, необходимое на горизонтальные и вертикальные перемещения по этажам между лестницами.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

using namespace std;

int _abs(int x)

{

return (x > 0) ? x : -x;

}

class BrokenElevator

{

public:

int wayTime(vector<string> plan)

{

int sx, sy, fx, fy, i, j, res, temp;

for(sx = sy = fx = fy = i = 0; i < plan.size(); i++)

for(j = 0; j < plan[0].size(); j++)

{

if (plan[i][j] == 'S') sx = i, sy = j;

if (plan[i][j] == 'F') fx = i, fy = j;

}

if (sx == fx) return 2 * _abs(sy - fy);

// Time spent on the stairs

res = _abs(sx - fx) / 2;

if (sx > fx)

{

temp = sx; sx = fx; fx = temp;

temp = sy; sy = fy; fy = temp;

res *= 3;

}

// Time spent on the Start floor

res += 2 * _abs(plan[sx+1].find('|') - sy);

// Time spent on the Finish floor

res += 2 * _abs(plan[fx-1].find('|') - fy);

for (i = sx + 1; i < fx - 1; i += 2)

res += 2 * _abs(plan[i].find('|') - plan[i+2].find('|'));

return res;

}

};