Задача
Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из [latex]n[/latex] его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.
Определите, побывал ли король дважды на одном и том же поле за свои [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].
Тесты
| Входные данные | Выходные данные |
| [latex]5[/latex] [latex]1[/latex] [latex]2[/latex] [latex]4[/latex] [latex]7[/latex] [latex]4[/latex] | [latex]4[/latex] |
| [latex]5[/latex] [latex]1[/latex] [latex]2[/latex] [latex]4[/latex] [latex]6[/latex] [latex]4[/latex] | [latex]Ok[/latex][latex]2[/latex] |
| [latex]8[/latex] [latex]3[/latex] [latex]3[/latex] [latex]7[/latex] [latex]7[/latex] [latex]5[/latex] [latex]5[/latex] [latex]3[/latex] [latex]3[/latex] | [latex]3[/latex] |
| [latex]7[/latex] [latex]2[/latex] [latex]4[/latex] [latex]2[/latex] [latex]8[/latex] [latex]8[/latex] [latex]1[/latex] [latex]5[/latex] | [latex]Ok[/latex][latex]3[/latex] |
| [latex]12[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex] [latex]1[/latex] [latex]3[/latex] [latex]2[/latex] [latex]5[/latex] [latex]6[/latex] [latex]8[/latex] [latex]2[/latex] [latex]1[/latex] [latex]7[/latex] | [latex]10[/latex] |
Код программы
|
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 47 48 49 50 |
#include <iostream> #include <cmath> using namespace std; int x[2001][2001]; int main() { int n; cin>>n; int move; int xPos=1001, yPos=1001; for(int i=0; i<n; i++) { cin>>move; if(x[xPos][yPos]==1) { cout<<i; return 0; } else x[xPos][yPos]=1; if(move==1) { xPos--; yPos++; } if(move==2) { yPos++; } if(move==3) { xPos++; yPos++; } if(move==4) { xPos++; } if(move==5) { xPos++; yPos--; } if(move==6) { yPos--; } if(move==7) { xPos--; yPos--; } if(move==8) { xPos--; } } cout<<"Ok"<<endl<<abs(xPos-1001)+abs(yPos-1001); return 0; } |
Решение задачи
Создаем глобальный массив(изначально заполненный нулями). Задаем координаты короля по центру int xPos=1001, yPos=1001;. Затем в цикле вводим все ходы короля и проверяем был ли он уже в этой ячейке, если нет — ставим [latex]1[/latex], и вводим ход короля и задаем ему новые координаты, если да — выводим номер хода и завершаем программу. Если король ни разу не попал на ячейку, в которой уже был, то программа находим манхэттенское расстояние между начальными координатами и конечными. Задача решена.
Ссылки
Условие задачи на e-olymp
Код решения на ideone.com
Здравствуйте, у вас в 4-м тесте ошибка. Правильный ответ должен быть 7, потому что на этом ходу король ходит в ту клетку, в которую пошел в предыдущем.