e-olymp 4557. Одинокий король

Задача взята с сайта e-olymp.

Задача


Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из $n$ его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.
Определите, побывал ли король дважды на одном и том же поле за свои [latex] n [/latex] ходов.

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

В первой строке задано общее число ходов короля [latex] n [/latex] [latex](0 ≤ n ≤ 1000)[/latex]. В последующих [latex] n [/latex] строках заданы направления перемещения короля: строка под номером [latex] i + 1 [/latex] задаёт направление перемещения короля на [latex]i[/latex]-ом ходу.

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

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.
Напоминаем, что манхэттенское расстояние между точками с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] определяется по формуле: [latex]d = |x_2 — x_1| + |y_2 — y_1|[/latex].

Тесты

# Входные  данные Выходные данные
1 5 1 2 4 7 4 4
2 5 1 2 4 6 4 Ok 2
3 3 1 2 1 Ok 5
4 3 1 5 1 2
5 8 8 8 8 8 8 8 8 8 Ok 8

Код

Решение

За изначальное местоположение короля возьмем точку с координатами [latex](0, 0)[/latex], а все передвижения короля по шахматной доске — это изменение абсциссы и (или) ординаты данной точки. Создадим два динамических массива  x = new int [n];  и  y = new int [n]; на [latex] n [/latex] элементов каждый, для абсцисс и ординат соответственно. Они будут хранить изменения координат всех точек, в которых побывал король. При этом, так как мы считаем, что начинаем движение с начала координат начнем заполнение массивов со второго элемента. Когда массивы в цикле  for (int i = 1; i <= n; i ++);  заполнятся будем искать совпадающие точки в другом цикле, если же таких не найдется, посчитаем расстояние между конечным и начальным местоположением короля, однако так как начальное местоположение короля — это начало координат, то ограничимся лишь немного упрощенной формулой [latex]d = |x_n| + |y_n|[/latex], или же в коде это выглядит так:  abs(x[n]) + abs(y[n]);. После, не забываем удалить уже использованные массивы, чтобы освободить память.

Код 2

Решение 2

Данный способ будет отличаться тем, что в отличии от предыдущего решения мы ограничимся лишь одним массивом, содержащим попарно координаты абсцисс и ординат соответственно. Также операторы  if(); можно заменить массивами  X[]; и  Y[]; , которые на соответствующих местах уже содержат изменение абсциссы и ординаты положения короля при конкретном перемещении.

Код 3

Решение 3

Изначально создаем двумерный массив заполненый нулями. Однако будем считать изначальное положение короля в точке с координатами [latex](1001, 1001)[/latex], чтобы не было проблем с отрицательными значениями. В данном варианте кода для большей краткости и разнообразия будем использовать оператор  switch();. Если король в клетке не был, то поставим [latex]1[/latex], если же был — выводим номер хода. Высчитываем манхэттенское расстояние если король не был в одной точке дважды.

Ссылки

  • Засчитанное решение 1 на e-olymp.
  • Засчитанное решение 2 на e-olymp.
  • Засчитанное решение 3 на e-olymp.
  • Код 1 в ideone.
  • Код 2 в ideone.
  • Код 3 в ideone.

12 thoughts on “e-olymp 4557. Одинокий король

  1. Для кодирования возможных шахматных (и аналогичных им) ходов есть классический подход, позволяющий избавиться от if-ов. Выглядит он приблизительно так:

    Это позволяет закодировать возможные ходы компактно в одном месте и дальше использовать их, не боясь набажить. Вместо двух массивов можно использовать массив пар, поскольку сдвиги по $x$ и $y$ являются логически связанными.

    Ваше решение работает за $O\left(n^2\right)$, что укладывается в ограничения данной задачи, однако существуют решения за $O\left(n\cdot\log n\right)$ и даже за $O\left(n\right)$. На собеседовании в Гугл у Вас о них спросят обязательно.

    В решении за $O\left(n^2\right)$ во вложенном цикле условие j < n && j != i избыточно.

    • Благодарю за замечания, поправил условие в цикле и добавил вариант кода с иным подходом для заполнения уже одного массива пар. Насчёт более быстрой работы программы пока что идей нет, но обязательно подумаю.

    • За $O\left(n\log n\right)$ мы научимся решать, когда будем учить класс set. Тогда сможем хранить путь в виде множества и вставлять за логарифмическое время. Я проверил, такой вариант уже позволил попасть в таблицу рекордов.
      Про линейную сложность у меня есть варианты.
      — Можно просто отмечать на доске места, где уже был. Но тогда нужна квадратичная память для хранения всей доски. Кроме того, из-за прыжков по памяти работать должно медленно если не написать работу с битовыми полями размером $(2n+1)\times(2n+1)$.
      — Второй вариант снова рассчитан на множества. Если правильно подобрать компаратор, то вставка будет проходить за время близкое к $O\left(1\right).$
      А какие у Вас идеи?

    • Ссылки ведут на задачу про вышивку крестиком. Исправьте.
    • В первом коде Вы 8 раз пишите одни и те же две строки. Я бы вынес их из условных операторов. И добавил else.
    • Кстати, хоть не люблю оператор switsh, но обязан признать — тут прямо под него всё заточено:

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