Задача 9.
Одинокий король долго ходил по бесконечной шахматной доске. Известна последовательность из N его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.).Написать программу, определяющую побывал ли король дважды на одном и том же поле за минимально возможное при заданном N число вычислений.
|
Решение задачи 9.
Будем хранить в массиве A[1..N,1..2] координаты тех клеток, где король уже был. Возьмем N достаточно большим, N=500. A[i,1] - иксовая, A[i,2] - игрековая координата клетки. Пусть в переменной DLN хранится количество уже сделанных ходов (т.о. в массиве A после хода номер i будут заняты клетки с первой по i-ую).
Результаты очередного хода заносим в массив A на первое свободное место (т.е. на место с индексом DLN+1), увеличиваем количество сделанных ходов DLN:=DLN+1, и проверяем, совпадает ли хоть одна из позиций, на которых король уже был, с текущей позицией:
for i:=1 to DLN-1 do
if (A[i,1]=A[DLN,1]) and
(A[i,2]=A[DLN,2]) {проверка совпадения}
then begin
writeln('совпадение на ходах ',DLN,' и ',i);
halt; {останов}
end;
Давайте посмотрим, как можно вводить ходы короля. Он из клетки k может пойти на 8 соседних позиций.
1
2
3
Будем вводить направление перемещения короля
8
K
4
цифрой от 1 до 8.
7
6
5
Заведем массив XOD=array[1..8,1..2]=((-1,1),(0,1),(1,1),
(1,0),(1,-1),(0,-1),(-1,-1),(-1,0));
В массив заносятся смещения по x- и y-координатам, соответствующие направлениям от 1 до 8. Координаты короля после сделанного хода вычисляются по формулам
x:=x+XOD[i,1]; y:=y+XOD[i,2];
|
