Задача
Прямоугольную комнату размерами [latex] m [/latex] на [latex] n [/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.
За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex] a [/latex] на паркетину [latex] b [/latex].
Входные данные
Во входном файле в первой сроке через пробел заданы значения [latex]m[/latex], [latex]n[/latex] [latex]\left ( 1\leqslant n,m\leqslant 100 \right )[/latex], а во второй — [latex] a [/latex] и [latex] b [/latex].
Выходные данные
Искомое количество шагов
Тесты
| # |
Входные данные |
Выходные данные |
| 1 |
5 4 25 38 |
5 |
| 2 |
5 4 6 22 |
4 |
| 3 |
5 4 15 22 |
3 |
| 4 |
3 2 1 12 |
7 |
| 3 |
5 4 15 22 |
3 |
| 5 |
3 2 6 12 |
2 |
Код 1
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 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void swap(int A, int B) { int C = A; A = B; B = C; } public static void main (String[] args) throws java.lang.Exception { int vertSize; int horSize; int firstNumber; int lastNumber; Scanner in = new Scanner(System.in); horSize = in.nextInt(); vertSize = in.nextInt(); firstNumber = in.nextInt(); lastNumber= in.nextInt(); if (firstNumber > lastNumber){ int C = firstNumber; firstNumber = lastNumber; lastNumber = C; } //вычисление координат int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1; int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1; int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1; int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1; //создание и задание размера для статического массива int[] Search= new int[2 * horSize]; Search[firstNumberx - 1] = 0; int step = 1; for (int i = firstNumberx - 2; i >= 0; i--){ Search[i] = step++; } step = 1; for (int i = firstNumberx; i < 2 * horSize; i++){ Search[i] = step++; } //сравнение по у for (int j = firstNumbery; j < lastNumbery; j++) { for (int i = 1; i < 2 * horSize; i += 2) { Search[i - 1] = Search[i] + 1; Search[i] += 2; //определение значения на предпоследнем элементе if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){ Search[i - 2] = Search[i]; } } } System.out.println(Search[lastNumberx - 1]); } } |
Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber [/latex] и [latex]lastNumber[/latex]. Следующим шагом будет определение позиции [latex]firstNumber [/latex] и [latex]lastNumber[/latex]. Положим, что [latex]x[/latex] — это позиция в строке, а [latex]y[/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем массив, переменные в котором будет иметь тип [latex]int[/latex] , а размер будет фиксированный. Для определения количества шагов заведем переменную с типом [latex]int[/latex].
Важно отметить, что идея решения данного способа состоит в том, чтобы на позиции [latex]Search[firstNumberx — 1][/latex] стояло количество шагов, совершенных в ходе решения.
Код 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { long m, n, a, b; Scanner in = new Scanner(System.in); m = in.nextLong(); n = in.nextLong(); a = in.nextLong(); b = in.nextLong(); long dm = ((a + 1)/2 - 1) %m - ((b + 1)/2 - 1) % m; long dn = (a - 1)/(2 * m) - (b - 1)/(2 * m); long o = dm * dn < 0? Math.min(Math.abs(dm), Math.abs(dn)) : 0; long k = dm > 0? 1: -1; a += 2*k*o*(m - 1); System.out.print( ((a + b) % 2 == 0? 0: Math.max(a, b) % 2 == 0? 1: -1) + 2*(Math.abs(dm) + Math.abs(dn) - o)); } } |
Ссылки
Задача на e-olymp
Код_1 задачи на ideone
Код_2 задачи на ideone
