Постановка задачи
Ссылка на задачу с сайта e-olymp
Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из [latex]n[/latex] клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче.
Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.
Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток [latex]n[/latex] и [latex]b[/latex] в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из [latex]a[/latex] в [latex]b[/latex].
Входные данные:
Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква ([latex]a[/latex]—[latex]h[/latex]), задающая столбец и второй – цифра ([latex]1[/latex]—[latex]8[/latex]), задающая строку на шахматной доске.
Выходные данные:
Для каждого теста вывести одну строку следующего содержания: «Путь от xx к yy занимает n шагов»
Тест
|
Решение
|
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. На экран выводим количество шагов, которые необходимо сделать конем, чтобы попасть из одной клетки в другую.