Олимпиадный тренинг

Задача . Unlocking Blocks


Задача

Темы: поиск в глубину и подобное

Коровы любят головоломки. Фермер Джон подарил Беси на день рождения новую головоломку. Она состоит из трех твердых объектов, каждый из которых состоит из склеенных вместе квадратиков размера 1 х 1. Каждый из этих объектов имеет «связную» форму в том смысле, что Вы можете перейти из одного квадратика в любой другой, двигаясь по квадратикам этого объекта в одном из четырех направлений: север, юг, запад, восток.
Объект может перемещаться последовательно скольжением на одну единицу в одном из четырех направлений: север, юг, запад, восток. Цель головоломки - переместить объекты так, чтобы они разделились – то есть, чтобы граничные квадратики отошли друг от друга. Ваша задача – по заданным трем объектам определить, можно их разделить, или нет. Конфигурация, которую разделить нельзя, называется заблокированной.

Замечание: программы, которые не делают ничего, кроме угадывания ответа, могут быть дисквалифицированы.
PROBLEM NAME: unlock
Формат входных данных
* Строка 1: Три разделенных одиночными пробелами целых числа: N1, N2, and N3, описывающих количество квадратов соответственно в фигурах 1, 2, и 3.
* Строки 2..1+N1: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 1. Все координаты в интервале 0..9.
* Строки 2+N1..1+N1+N2: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 2. Все координаты в интервале 0..9.
* Lines 2+N1+N2..1+N1+N2+N3: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 1. Все координаты в интервале 0..9.
Формат выходных данных
* Строка 1: Выведите 1, если объекты могут быть отделены друг от друга, и 0 в противном случае.
Примеры
№Входные данныеВыходные данные
1 
12 3 5
0 0
1 0
2 0
3 0
3 1
0 1
0 2
0 3
0 4
1 4
2 4
3 4
2 1
2 2
1 2
2 3
3 3
4 3
4 4
4 2
 
1
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет