Постановка задачи. Лабиринт задан таблицей n*m из символов. Символ '#' - означает стену, '.' - пустое пространство, 's' - начальную позицию, 'f' - конечную позицию. Игрок может находиться только в пустых клетках. Из клетки он может перемещаться в соседнюю по горизонтали или по вертикали, но не по диагонали. Требуется найти кратчайший путь из начальной клетки в конечную.
Пример лабиринта и кратчайшего пути в нем (n=4, m=6):
...... 23456. s#.#.. 1#.#7. .#.#.. .#.#8. ...#f. ...#9.
Решение. Для решения используется алгоритм поиска в ширину. Собственно, поиском в ширину его обычно называют, когда говорят про графовые алгоритмы. В задачах о лабиринтах его чаще называют волновым алгоритмом, или просто волной.
// -------------------------------------------------------------------------
// lab - двухмерный массив, в котором хранится лабиринт
// n,m - количество строк и столбцов в массиве lab
// si,sj - начальная позиция
// fi,fj - конечная позиция
typedef struct point {int i, j;} point;
int di[4] = { -1, 0, 1, 0};
int dj[4] = { 0, 1, 0, -1};
int i,j;
int d[n][m]; // массив расстояний
int head,tail; // указатели очереди
point queue[n*m]; // очередь
// обнуляем массив расстояний
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
d[i][j] = 0;
d[si][sj] = 1; // расстояние до начальной клетки равно 1
// инициализируем очередь
head = tail = 0;
queue[tail].i = si;
queue[tail++].j = sj; // заносим в очередь начальную клетку
while (head < tail) // цикл пока очередь не пуста
{
point p = queue[head++]; // берем следующую позицию из очереди
for (int k = 0; k < 4; k++) // цикл по соседним клеткам
{
point newp;
newp.i = p.i + di[k];
newp.j = p.j + dj[k];
// проверяем, что такая клетка есть
if (0 <= newp.i && newp.i < n && 0 <= newp.j && newp.j < m)
// проверяем, что она свободна и ранее ее не посещали
if (lab[newp.i][newp.j] != '#' && d[newp.i][newp.j] == 0)
{
d[newp.i][newp.j] = d[p.i][p.j] + 1; // находим расстояние
queue[tail++] = newp; // заносим позицию в очередь
}
}
}
if (d[fi][fj])
printf("расстояние = %d\n", d[fi][fj]);
else
printf("нет ни одного пути");
// -------------------------------------------------------------------------
Массив d используется для хранения расстояний от начальной клетки до каждой из остальных. Если d[i][j] = 0, то расстояние до клетки (i,j) еще неизвестно. Клетки обрабатываются в порядке увеличения расстояния. Для этого используется очередь. При обработке клетки в очередь заносятся все соседние с ней, расстояние до которых еще не известно. Причем расстояние до них устанавливается равным расстоянию до текущей клетки плюс один.
Рассмотрим работу алгоритма на приведенном выше примере. Порядок занесения клеток в очередь будет следующий: (1,0), (0,0), (2,0), (0,1), (3,0), (0,2), (3,1), (0,3), (1,2), (3,2), (0,4), (2,2), (0,5), (1,4), (1,5), (2,4), (2,5), (3,4), (3,5).
Значения элементов массива d:
...... 2 3 4 5 6 7 s#.#.. 1 0 5 0 7 8 .#.#.. 2 0 6 0 8 9 ...#f. 3 4 5 0 9 10
Приведенный выше алгоритм находит только длину кратчайшего пути. Сам путь можно восстановить с конца с помощью массива d. Последней клеткой в пути будет (fi,fj). Предпоследняя клетка (i,j) - это одна из соседних с (fi,fj) клеток, для которой d[i][j] = d[fi][fj] - 1. Затем выбираем клетку, соседнюю с предпоследней, расстояние до которой равно d[fi][fj] - 2, и так далее, пока не дойдем до (si,sj).