Практика программирования (Бейсик, Си, Паскаль)



         

Задачи, советы и ответы - часть 6


b:array [1..4,1..4] of integer = ((1,2,3,4), (5,6,7,8), (9,10,11,12), (13,14,15,16));

procedure printa(row,col,w:integer,-var с;n,m:integer);

var

j,k:integer;

d:array [0..MaxInt-l] of integer absolute c;

begin

for j:=0 to n-1 do

for k:=0 to m-1 do

begin

gotoxy(col+k*w,row+j); write(d[k+m*j]:w);

end;

end;

begin clrscr;

printa(5, 5, 4, a, 3, 4);

printa(5, 40, 5, b, 4, 4);

readln;

end.

Задание 4.06. Ход конем

Существует довольно много комбинаторных задач, связанных с шахматным полем. Это и задача о расстановке восьми ферзей, которые бы не угрожали друг другу, т. е. чтобы ни одна из пар не находилась на общей вертикали, горизонтали и диагонали. Это и различные путешествия коня по шахматному полю. Среди них — построение траектории ходов, при которых конь, начиная из заданной позиции, обходит все клетки поля, не заходя повторно в уже пройденные. Или — заданы начальная и конечная позиции, и нужно построить одну или все траектории между указанными клетками, содержащие минимальное число ходов. Самая простая среди "лошадиных" задач заключается в определении минимального количества ходов, за которое конь может добраться из начальной позиции в конечную. Именно ей и посвящено очередное задание.

Говорят, что конь ходит буквой "Г". Это не совсем точно, т. к. допустимые ходы этой фигуры образуются перемещениями на две клетки по горизонтали (вертикали) с последующим поворотом на 90 градусов по или против часовой стрелки и сдвигом по вертикали (горизонтали) еще на одну клетку. Если сопоставить с шахматной доской матрицу 8x8, то из позиции a[i,j] возможны максимум 8 ходов в клетки со следующими индексами:

1. a[i-2,j-1] 5. a[i+l,j-2]

2. a[i-2,j+l] 6. a[i+l,j+2]

3. a[i-l,j-2] 7. a[i+2,j-1]

4. a [i-1,j+2] 8. a[i + 2,j + 1]

По мере приближения к границам поля какие-то из этих перемещений становятся недопустимыми из-за выхода некоторых индексов за пределы установленного диапазона. Минимальным числом ходов, равным 2, обладают угловые клетки шахматной доски.




Содержание  Назад  Вперед