Задача взята с сайта 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 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> #include <cmath> using namespace std; int main() { int *x, *y, n, pos, x1 = 0, y1 = 0; bool f = true; cin >> n; x = new int [n]; y = new int [n]; for (int i = 1; i <= n; i ++){ cin >> pos; if (pos == 1){ x1 -= 1; y1 += 1; } else if (pos == 2) y1 += 1; else if (pos == 3){ x1 += 1; y1 += 1; } else if (pos == 4) x1 += 1; else if (pos == 5){ x1 += 1; y1 -= 1; } else if (pos == 6) y1 -= 1; else if (pos == 7){ x1 -= 1; y1 -= 1; } else if (pos == 8) x1 -= 1; x[i] = x1; y[i] = y1; } for (int i = 1; i < n && f; i++) for (int j = 0; j < i; j++) if ((x[i] == x[j]) && (y[i] == y[j])){ cout << i; f = false; } if (f) cout << "Ok" << endl << abs(x[n]) + abs(y[n]); delete []x; delete []y; return 0; } |
Решение
За изначальное местоположение короля возьмем точку с координатами [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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <cmath> using namespace std; int main() { int *x, n, pos, x1 = 0, y1 = 0; bool f = true; cin >> n; int X[] = {-1, 0, 1, 1, 1, 0, -1, -1}; int Y[] = {1, 1, 1, 0, -1, -1, -1, 0}; x = new int [2*n+2]; for (int i = 2; i < (2 * n + 2); i += 2){ cin >> pos; x1 += X[pos-1]; y1 += Y[pos-1]; x[i] = x1; x[i+1] = y1; } for (int i = 0; i < (2 * n + 2) && f; i += 2) for (int j = 0; j < i; j += 2) if ((x[i] == x[j]) && (x[i+1] == x[j+1])){ cout << i / 2; f = false; } if (f) cout << "Ok" << endl << abs(x[2*n+1]) + abs(x[2*n]); delete []x; return 0; } |
Решение 2
Данный способ будет отличаться тем, что в отличии от предыдущего решения мы ограничимся лишь одним массивом, содержащим попарно координаты абсцисс и ординат соответственно. Также операторы if(); можно заменить массивами X[]; и Y[]; , которые на соответствующих местах уже содержат изменение абсциссы и ординаты положения короля при конкретном перемещении.
Код 3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <cmath> using namespace std; int x[2001][2001]; int main() { int n; cin >> n; int pos; bool f = true; int x1 = 1001, y1 = 1001; for (int i = 0; i< n && f; i++){ cin >> pos; if(x[x1][y1] == 1){ cout << i; f = false; } else x[x1][y1] = 1; switch (pos){ case 1: x1--; y1++; break; case 3: x1++; case 2: y1++; break; case 4: x1++; break; case 5: x1++; case 6: y1--; break; case 7: y1--; case 8: x1--; } } if (f) cout << "Ok" << endl << abs(x1-1001) + abs(y1-1001); return 0; } |
Решение 3
Изначально создаем двумерный массив заполненый нулями. Однако будем считать изначальное положение короля в точке с координатами [latex](1001, 1001)[/latex], чтобы не было проблем с отрицательными значениями. В данном варианте кода для большей краткости и разнообразия будем использовать оператор switch();. Если король в клетке не был, то поставим [latex]1[/latex], если же был — выводим номер хода. Высчитываем манхэттенское расстояние если король не был в одной точке дважды.
Ссылки
- Засчитанное решение 1 на e-olymp.
- Засчитанное решение 2 на e-olymp.
- Засчитанное решение 3 на e-olymp.
- Код 1 в ideone.
- Код 2 в ideone.
- Код 3 в ideone.
Для кодирования возможных шахматных (и аналогичных им) ходов есть классический подход, позволяющий избавиться от 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).$
А какие у Вас идеи?
Про $O\left(n\cdot\log n\right)$ полностью солидарен. В случае $O\left(n\right)$ нам понадобится хеш-таблица с $O\left(n\right)$ памяти.
Cпасибо за идею со switch, оно и в правду было бы здесь лучше, но решил уже оставить с if. Убрал в первом коде добавление элементов в массив в каждом if, вынес это в конец цикла. Единственное, не понятно зачем использовать еще и else. Поправил ссылки.
Без else происходит следующее. Убедившись, что pos == 1 и выполнив необходимые действия, Вы проверяете а вдруг он ещё и равен 2, 3, 4, 5, 6, 7 и 8. А как такое может случиться, если переменная меняется только при вводе.
Стоит воспользоваться комбинацией else if.
Да, не учел этого, спасибо
Ок.
А ++ и -- Вы специально не используете?
В предыдущий кодах не использовал, думал так будет нагляднее. В третьем сделал так.
Владимир, уберите лишний переход на новую строчку между пунктами: код и решение.
Благодарю за внимательность, поправил.