Дана шахматная
доска, состоящая из n×n клеток, несколько из них вырезано.
Провести ходом коня через невырезанные клетки путь минимальной длины из одной
клетки в другую.
Вход. В первой строке задано число n (2 ≤ n ≤
50). В следующих n строках содержится
по n символов. Символом # обозначена
вырезанная клетка, точкой – невырезанная клетка, символом @ – начальная и
конечная клетки пути коня (таких символов два).
Выход. Если путь построить невозможно, то вывести “Impossible”.
В противном случае вывести такую же карту, как и на входе, но пометить все
промежуточные положения коня символом @.
|
Пример входа |
Пример выхода |
5@..@...##...........
..... |
@..@. ..##. .@..@ ..@.. @.... |
графы –
поиск в ширину
Анализ алгоритма
Реализация алгоритма
int
dx[] = {1,1,-1,-1,2,2,-2,-2};
int dy[] = {2,-2,2,-2,1,-1,1,-1};
Позицию коня на доске будем хранить парой координат (x, y),
для этого объявим структуру CELL. Объявим операторы сравнения ячеек (“равно” и
“не равно”).
struct
CELL
{
int x, y;
CELL(int a = -1, int b = -1) : x(a), y(b) {};
};
int operator==(CELL a, CELL b)
{
return (a.x == b.x) && (a.y ==
b.y);
}
int operator!=(CELL a, CELL b)
{
return !((a.x == b.x) && (a.y ==
b.y));
}
Объявим массив предков Parent. Массив предков также будем использовать для запоминания
посещенных клеток шахматной доски. Если Parent[i][j] = (-1, -1), то
ячейка (i, j) еще не посещалась конем. Определим пустую ячейку EMPTY_CELL.
CELL EMPTY_CELL(-1,-1), Start(-1,-1),
Finish(-1,-1);
CELL
Parent[MAX][MAX];
Начальное состояние доски считываем в массив s.
char
s[MAX][MAX];
Функция CanGo возвращает 1,
если ячейка c не находится за
границей поля.
int
CanGo(CELL c)
{
return !((c.x < 0) || (c.x >= n)
|| (c.y < 0) || (c.y >= n));
}
Функция bfs запускает поиск
в ширину из ячейки Start. Объявим очередь d.
void
bfs(CELL Start)
{
deque<CELL> d;
d.push_back(Start);
s[Start.x][Start.y] = '#';
while(!d.empty())
{
Берем из головы очереди позицию типа Node.
Перебираем все возможные ходы коня из нее.
CELL Node = d.front(); d.pop_front();
for(int
k = 0; k < 8; k++)
{
CELL Next = CELL(Node.x + dx[k], Node.y + dy[k]);
Если ход совершается в позицию Next, которая находится за краями доски, то совершить его
невозможно.
if (!CanGo(Next)) continue;
Если позиция Next
представляет собой невырезанную клетку, и мы там еще не были, то идем туда. В
массиве предков отмечаем, что в Next
мы попали из вершины Node.
if ((s[Next.x][Next.y] != '#') &&
(Parent[Next.x][Next.y] ==
EMPTY_CELL))
{
Parent[Next.x][Next.y] = Node;
Если мы попали в конечную вершину Finish, то завершаем поиск.
if
(Next == Finish) return;
Заносим клетку Next
в конец очереди d.
d.push_back(Next);
}
}
}
}
Основная часть программы. Проводим инициализацию
переменных. Читаем состояние шахматной доски в массив s. Координаты начального
и конечного положения коня, отмеченные на доске символом @, заносим в
переменные Start и Finish типа CELL.
scanf("%d\n",&n);
for(i
= 0; i < n; i++) gets(s[i]);
for(i
= 0; i < n; i++)
for(j
= 0; j < n; j++)
if (s[i][j] == '@')
{
if (Start.x == -1) {Start.x = i; Start.y
= j;}
else {Finish.x = i; Finish.y = j;}
}
Запускаем поиск в ширину из клетки Start.
bfs(Start);
Поиск в ширину мы могли завершить по выполнению одного из
двух условий: либо просмотрены все вершины, куда можно попасть конем из клетки Start и очередь d стала пустой, либо в какой-то момент времени мы попали в Finish и вышли из функции bfs.
Если поиск в глубину не добрался до ячейки Finish, то искомого пути коня не существует.
if
(Parent[Finish.x][Finish.y] == EMPTY_CELL) printf("Impossible\n");
else
{
Если кратчайший путь из Start в Finish существует, то при помощи массива
предков восстанавливаем его. Кратчайший путь коня заполняем символами @.
s[Start.x][Start.y] = '@';
while(Start != Finish)
{
s[Finish.x][Finish.y] = '@';
Finish = Parent[Finish.x][Finish.y];
}
Выводим результирующую шахматную доску.
for(i = 0; i < n; i++) puts(s[i]);
}