|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
20.05.2019, 23:12 | #1 |
Пользователь
Регистрация: 08.05.2019
Сообщений: 27
|
Соответствие Входа и Примера
Здравствуйте
Сам алгоритм я понимаю как написать. Я не понимаю соответствие Входа и Примера. Что за что отвечает. Подскажите пожалуйста. Задания: Одно движение шахматного прыгуна (лошади) - это прыжок на два поля вертикально или горизонтально, а затем на один квадрат под прямым углом. Такое движение создает букву «Л». Все поля, доступные одним движением перемычки, отмечены крестиком на диаграмме ниже. Рассмотрим неограниченную шахматную доску, на которой стоит несколько перемычек и на которой выделено одинаковое количество целевых полей. После выполнения определенного количества ходов (описанных выше) перемычки должны находиться на целевых полях. Как это сделать, выполнив минимальное количество ходов? Задача Напишите программу, которая для заданного распределения выходных N перемычек и N целевых полей найдет минимальное количество ходов, после которого перемычки окажутся на целевых полях. Входные данные В первой строке стандартного ввода содержится целое число D (1 ≤D ≤ 20), обозначающее количество наборов данных, размещенных в следующих строках. Каждый набор состоит из строки, содержащей количество N перемычек (1≤N≤ 1000), и из следующих 2N строк, содержащих координаты выходных полей перемычек (N строк), а затем расположение целевых полей (следующие N строк). Каждая из 2N строк, содержащих координаты поля (выходной или целевой), содержит две, разделенные одним пробелом целые числа x, y (-2000000000≤x, y ≤ 2 000 000 000), обозначающие номера столбца и строки, соответственно, на пересечении какого поля. Выходные данные Стандартный выходной файл должен содержать D задач для последующих наборов данных. Каждое решение должно быть записано в одну строку, в которой должно быть одно положительное целое число K - обозначающее минимальное количество движений, необходимое для перемещения всех перемычек из начальной позиции в целевую позицию. //4 //1 //5 5 //5 6 //2 //0 0 //1 0 //0 1 //1 1 //13 //4 1 //4 2 //3 3 //0 7 //4 3 //6 1 //3 5 //6 3 //5 4 //2 7 //3 7 //5 6 //7 5 //1 1 //3 0 //4 0 //1 4 //3 2 //0 7 //3 5 //7 3 //6 6 //7 5 //5 7 //7 6 //6 7 //15 //0 0 //0 1 //1 1 //2 0 //0 3 //3 3 //5 2 //7 0 //1 7 //3 6 //6 4 //7 4 //7 5 //6 7 //7 7 //1 1 //0 3 //4 0 //3 2 //2 3 //6 1 //0 7 //1 6 //3 5 //5 3 //4 4 //7 3 //4 7 //5 7 //7 7 правильный ответ: //3 //4 //18 //24 |
21.05.2019, 09:25 | #2 | |||
Старожил
Регистрация: 20.04.2008
Сообщений: 5,526
|
Цитата:
В первой строке стандартного ввода содержится целое число D (1 ≤D ≤ 20), обозначающее количество наборов данных D=//4 Каждый набор состоит из ... строки, содержащей количество N перемычек (1≤N≤ 1000) N[1]=//1 из следующих 2N строк 2*N[1]=2*1 =2 содержащих координаты выходных полей перемычек (N строк) N[1]=1 //5 5 а затем расположение целевых полей (следующие N строк) N[1]=1 //5 6 ---конец набора N[1] N[2]=//2 ... N[3]=... .... N[4{=D}]=... ... --конец данных Цитата:
Цитата:
D=//3 ??? видимо один из наборов НЕ ИМЕЕТ решения. (а какой?.. X) и о таком поведении вывода правильно предупреждать в описании(постановке задачи). N[1?] =//4 хода N[2?] =//18 N[3?] =//24 N[4?X] --------
программа — запись алгоритма на языке понятном транслятору
Последний раз редактировалось evg_m; 21.05.2019 в 09:36. |
|||
21.05.2019, 09:37 | #3 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
|
21.05.2019, 21:49 | #4 |
Пользователь
Регистрация: 08.05.2019
Сообщений: 27
|
Забыл добавить)
|
21.05.2019, 21:51 | #5 | |
Пользователь
Регистрация: 08.05.2019
Сообщений: 27
|
Цитата:
Всё равно не понял) |
|
21.05.2019, 23:16 | #6 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,309
|
Есть неограниченное шахматное поле, на котором задано положение нескольких коней и соответствующее им число позиций, на которые кони должны встать за минимальное число ходов.
Координаты полей задаются в системе XY. Левое нижнее поле имеет координаты - 0 0. Первым числом задаётся число вариантов размещения коней. В каждом варианте задаётся число коней, координаты их начальных положений и координаты полей, на которые кони должны переместиться за минимальное число ходов. В примере: Первое поле - число вариантов - 4. Вариант 1: Число коней - 1. Конь находится в позиции - 5 5 Конь должен оказаться в позиции 5 6 Вариант 2: число коней - 2. Конь 1 находится в позиции - 0 0 Конь 2 находится в позиции - 1 0 Кони должны оказаться в позициях 0 1 и 1 1 Каким образом кони займут эти позиции неважно. Важно, что бы число ходов было минимальным.
Как-то так, ...
|
22.05.2019, 09:21 | #7 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
ну, должен ли именно первый конь оказаться на первом целевом поле а второй - на втором. Рискну предположить, что нет, кони вообще не различаются. Т.е. может быть, что быстрее поставить второго коня на первое целевое поле, а второго - на первое. |
|
22.05.2019, 20:08 | #8 |
Пользователь
Регистрация: 08.05.2019
Сообщений: 27
|
Спасибо, теперь всё понял.
Буду думать теперь как решить |
22.05.2019, 20:52 | #9 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,309
|
Добавлю ещё немного.
При перемещении коней может случиться так, что конь должен пройти через поле, на котором уже или ещё стоит конь. Из условия неясно, как это должно учитываться. Если конь может ходить только по свободным полям, то как вариант, надо смотреть и возможность смены порядка ходов.
Как-то так, ...
|
23.05.2019, 19:45 | #10 |
Пользователь
Регистрация: 08.05.2019
Сообщений: 27
|
У меня появился вопрос
Что должно быть в ответе? Например в первом наборе данных всё правильно, конь достигает цели за три хода, выписывается 3. Во втором наборе не понятно откуда взялось 4, потому что первый конь достигает цели за 3 хода и второй тоже за 3. Откуда взялось 4? |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Prolog. Задачи на соответствие | C++++ | Помощь студентам | 0 | 06.01.2016 23:22 |
Неточное соответствие ВПР | s8259 | Microsoft Office Excel | 11 | 11.12.2015 01:18 |
Соответствие условию | netfilter | Общие вопросы C/C++ | 1 | 10.12.2012 14:00 |
проверить XML на соответствие схеме XSD | LISTAT | Общие вопросы Delphi | 0 | 24.09.2012 14:22 |
не соответствие типов | amandra | SQL, базы данных | 6 | 30.06.2008 18:04 |