A[i,j]=false - клетка
A[i,j]=false - клетка черная*}
B:array[1..N,1..N] of integer;{* начальное значение B[i,j]=-1 для всех значений i и j, B[i,j]=p, где p>0 означает, что в клетку <i,j> можно попасть за p перемещений*}
Формирование значений элементов матрицы А очевидно, с матрицей В чуть сложнее. Определим понятие метки (p). Ее начальное значение равно 1. Пусть мы пометили некоторую клетку значением метки, равным p, тогда при нахождении клетки, в которую мы можем попасть из рассматриваемой клетки за один шаг, метим ее значением на единицу большим, считаем необработанной и помещаем в очередь. Использование очереди для запоминания «необработанных» клеток (по принципу обхода в ширину, глава 3) делает логику более строгой, чем очередной просмотр матрицы для поиска клеток, помеченным текущим значением метки.
Так, для следующего примера матрица B имеет вид:
Мы нашли длину минимального пути, но пока еще не сам путь. Для рассматриваемого примера его значение равно 17 и оно записано в B[1,N]. Для
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
