Задача с сайта e-olimp №2820. Перемещение коня
Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из n клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче.
Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.
Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток a и b в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из a в b.
Входные данные
Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква (a—h), задающая столбец и второй – цифра (1—8), задающая строку на шахматной доске.
Выходные данные
Для каждого теста вывести одну строку следующего содержания: «To get from xx to yy takes n knight moves.» (см. пример выходных данных).
Тесты:
| Пример входных данных | Пример выходных данных |
| e2 e4 | To get from e2 to e4 takes knight 2 moves. |
| a1 b2 | To get from a1 to b2 takes knight 4 moves. |
| b2 c3 | To get from b2 to c3 takes knight 2 moves. |
| a1 h8 | To get from a1 to h8 takes knight 6 moves. |
| a1 h7 | To get from a1 to h7 takes knight 5 moves. |
| h8 a1 | To get from h8 to a1 takes knight 6 moves. |
| b1 c3 | To get from b1 to c3 takes knight 1 moves. |
| f6 f6 | To get from f6 to f6 takes knight 0 moves. |
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<cstdio> #include<queue> using namespace std; char a, b; int nx, ny, tx, ty; int mx[] = { -1, -1, 1, 1, -2, -2, 2, 2 }; int my[] = { 2, -2, 2, -2, 1, -1, 1, -1 }; int A[8][8]; int main() { while(scanf("%c%d %c%d\n", &a, &ny, &b, &ty) == 4) { nx = a - 'a'; ny--; tx = b - 'a'; ty--; A[nx][ny] = 0; queue< pair<int, int> > q; q.push(make_pair(nx, ny)); while(!q.empty()) { pair<int, int> c = q.front(); int x = c.first, y = c.second; if(x == tx && y == ty) break; q.pop(); for(int i = 0; i < 8; i++) { if(x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) { q.push(make_pair(x + mx[i], y + my[i])); A[x + mx[i]][y + my[i]] = A[x][y] + 1; } } } printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]); } } |
Данную задачу можно решить с помощью алгоритма поиска в ширину. Из начальной клетки мы ищем все возможные ходы пока не попадем в нужную клетку. Чтобы получить длину пути, нужно хранить длины путей до данной клетки в матрице и обновлять ее, по ходу продвижения (если новое значение меньше того, что записано в клетке — записываем его, а если больше — оставляем предыдущее). Длина в начальной клетке — 0, а длина в каждой последующей — 1.
Ссылка на засчитанное решение и код решения на ideone.