Постановка задачи
Ссылка на задачу с сайта e-olymp
Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из n клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче.
Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.
Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток n и b в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из a в b.
Входные данные:
Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква (a—h), задающая столбец и второй – цифра (1—8), задающая строку на шахматной доске.
Выходные данные:
Для каждого теста вывести одну строку следующего содержания: «Путь от xx к yy занимает n шагов»
Тест
Пример входных данных |
Пример выходных данных |
e2 e4 |
Путь от e2 к e4 занимает 2 шагов. |
a1 b2 |
Путь от a1 к b2 занимает 4 шагов. |
b2 c3 |
Путь от b2 к c3 занимает 2 шагов. |
a1 h8 |
Путь от a1 к h8 занимает 6 шагов. |
a1 h7 |
Путь от a1 к h7 занимает 5 шагов. |
h8 a1 |
Путь от h8 к a1 занимает 6 шагов. |
b1 c3 |
Путь от b1 к c3 занимает 1 шагов. |
f6 f6 |
Путь от f6 к f6 занимает 0 шагов. |
|
Решение
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
|
import java.util.*; import java.lang.*; import java.util.regex.Matcher; import java.util.regex.Pattern; class Main { public static class Pair <T1, T2> { public T1 fst; public T2 snd; public Pair(T1 t1, T2 t2) { this.fst = t1; this.snd = t2; } } public static void main(String[] args) { 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[][] = new int[8][8]; Scanner s = new Scanner(System.in); String str; while (s.hasNextLine()) { String line = s.nextLine(); Pattern p = Pattern.compile("^(.)(\\d) (.)(\\d)$"); Matcher m = p.matcher(line); m.find(); a = m.group(1).toCharArray()[0]; ny = Integer.parseInt(m.group(2)); b = m.group(3).toCharArray()[0]; ty = Integer.parseInt(m.group(4)); nx = a - 'a'; ny--; tx = b - 'a'; ty--; A[nx][ny] = 0; Queue<Pair<Integer, Integer>> q = new LinkedList<Pair<Integer, Integer>>(); q.add(new Pair<Integer, Integer>(nx, ny)); while (!q.isEmpty()) { Pair<Integer, Integer> c = q.peek(); int x = c.fst, y = c.snd; if (x == tx && y == ty) break; q.remove(); 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.add(new Pair<Integer, Integer>(x + mx[i], y + my[i])); A[x + mx[i]][y + my[i]] = A[x][y] + 1; } } } System.out.printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]); } } } |
Ссылка на решение задания с сайта e-olymp
Ссылка на решение задания на онлайн компиляторе Ideone.com
Описание решения
Для начала объявим переменные
aи
b типа
char, где
a и
b — это координаты двух клеток. В цикле при помощи форматированного ввода по шаблону вводим 4 переменных, в которых
a,
ny — координата одной клетки и
b,
ty — координата другой клетки.
nx — цифровая координата, которую мы получаем из буквы, отнимая от
a. Создаем очередь, добавляем начальную клетку и ищем все возможные ходы пока не попадем в нужную клетку. Чтобы получить длину пути, нужно хранить длины путей до данной клетки в матрице и обновлять ее, по ходу продвижения. Длина в начальной клетке — 0, а длина в каждой последующей — 1. На экран выводим количество шагов, которые необходимо сделать конем, чтобы попасть из одной клетки в другую.