CodinGame | There is no Spoon - Episode 1 | C++

Приветствую! В этой интересной задачке мы посмотрим на пример применения перегрузки операторов.

Описание задачи: Игра ведётся на прямоугольной сетке с заданным размером. Некоторые ячейки содержат силовые узлы. Остальные ячейки пусты.

Нужно найти соседей каждого узла и соединить их между собой.

Техническое описание задачи:

Вы должны найти каждую (x1, y1) координату, содержащую узел, и отобразить (x2, y2) координаты следующего узла справа и (x3, y3) координаты следующего узла внизу в сетке. Если сосед не существует, вы должны вывести координаты -1 -1 вместо (x2, y2) и/или (x3, y3). Вы проиграете, если:

• передать неверные координаты соседнего узла;

• переданные координаты ячейки не содержат узла;

• происходит подсоединение к уже активированному узлу;

• не вычислить соседей узла.

Пример:

В этом примере поле 2х2 содержит одну пустую ячейку (1, 1).

00
0.

Узел в (0, 0) имеет 2 соседей.

0 0 1 0 0 1

Узел в (1, 0) не имеет соседей.

1 0 -1 -1 -1 -1

Узел в (0, 1) не имеет соседей.

0 1 -1 -1 -1 -1

Входные данные:

Программа должна сначала прочитать данные инициализации из стандартного ввода. Затем предоставить стандартному выводу одну строку-инструкцию.

Строка 1: ширина x. Строка 2: высота y. Следующие строки: матрица. Точка представляет пустую ячейку. Ноль представляет ячейку, содержащую узел.

Выходные данные:

Шесть целых чисел на одной линии: x1 y1 x2 y2 x3 y3

There is no Spoon - Episode 1 решение на С++:

Во-первых, подумаем как лучше всего организовать работу с координатами. Для этого отлично подойдёт простенькая структура с двумя полями.

Перегрузим оператор присваивания с защитой от самоприсваивания. Везде используем ссылки.

Во-вторых, нужно решить как искать соседний узел. В принципе, мы просто будем последовательно перебирать все ячейки cправа/снизу до тех пор пока не найдём узел. Нам необходимо изменять текущее местоположение. Для удобства перегрузим оператор += для структуры Position.

Обратите внимание, что этот код объясняет оператору += поведение в ситуации, когда справа от него оказывается переменная типа Position. Обязательно передаём правостоящий элемент по константной ссылке.

Аналогично перегружаем оператор вывода. Это нужно для удобного вывода координат. Я хочу хранить данный код внутри описания структуры Position, поэтому нужно сделать класс ostream дружественным классу Position. Затем в коде описан простенький конструктор структуры.

Теперь нам нужны несколько констант. EAST и SOUTH — шаг в сторону, ALONE — координата несуществующей позиции. WIDTH и HEIGHT — размерность матрицы. GRID — матрица, сетка, поле.

Считаем все данные в отдельной функции. Воспользуемся range-based циклом. Обязательно используем ссылку, чтобы не создавать копии объектов!

Создадим простенькую функцию, которая возвращает true, если текущая координата не выходит за границы поля. Функция isGrid принимает значение по константной ссылке!

Ещё одна функция. На этот раз проверяем, является ли текущая клетка узлом.

Самое интересное тут: рекурсивная функция, которая работает по-разному в зависимости от переданного ей направления. В нашем случае это либо EAST, либо SOUTH. Обратите внимание, что текущая координата постоянно изменяется, поэтому используем ссылку, пускай и не константную. В рекурсивных функциях особенно важно избегать постоянных передач объектов по значению.

Что делает функция directionalAnalysis:

1. переходит на следующую клетку;

2. если вышли за поле, значит соседей нет;

3. проверяет, является ли текущая клетка искомым узлом;

4. углубляет рекурсию.

Организуем грамотный проход по матрице, делая соответствующую проверку. Обратите внимание на то, что из-за ссылочной адресации в момент, когда мы вызываем функцию directionalAnalysis, мы не можем просто передать node. Иначе при вызове анализа следующего направления node, будучи изменённым, перестанет быть текущей координатой.

Итоговый код:

Послесловие:

Порешать задачи по программированию можно на CodinGame. -- © Bezukh Vladimir, 2019