Задача Newcutting
Хлопчині подарували чарівну коробку. Коробка має вигляд картонного куба з ребром N, грані якого розбиті на одиничні клітинки, кожну з яких зафарбовано певним кольором. Щоб відкрити коробку, хлопчина повинен зробити розріз по всіх лініях між клітинками ( включаючи ребра ), якщо ці дві клітинки мають різні кольори. Допоможіть хлопчині порахувати, на скільки фрагментів розпадеться коробка. Дві клітинки належать різним фрагментам, якщо неможливо пройти з однієї клітинки в іншу, не перетинаючи розрізи.
Технічні умови. Програма читає з клавіатури розмір коробки N (1<=N<=25). Наступні 3*N рядків містять номери кольорів розфарбування коробки. Розгортка коробки показана на малюнку. Перші N рядків описують розфарбування верхньої грані ( в кожному рядку N чисел), наступні N рядків описують передню, праву, задню та ліву грані (в кожному по 4*N чисел), далі N рядків описують розфарбування нижньої грані ( в кожному рядку N чисел). Всі числа розділено пропусками. Номери кольорів - натуральні числа, що не перевищують N3. Програма виводить на екран шукану кількість фрагментів.
Приклад
Вхід
3
1 1 1
1 1 1
1 1 1
1 1 1 4 4 4 1 1 1 3 3 3
2 2 1 4 4 4 1 3 1 3 1 3
1 1 1 4 4 4 1 1 1 3 3 3
1 1 1
1 1 1
1 1 1
Вихід
6
Задача Newcutting
Маленькому мальчику подарили волшебную коробку. Коробка является картонным кубом с ребром N, грани которого разбиты на единичные клетки, каждая клетка закрашена некоторым цветом. Чтобы открыть коробку, мальчик должен сделать разрез по всем линиям между клетками (включая ребра), если эти две клетки окрашены в разные цвета. Помогите мальчику подсчитать, на сколько фрагментов распадется коробка. Две клетки принадлежат разным фрагментам, если невозможно пройти из одной клетки в другую, не пересекая разрезы.
Технические условия. В первой строке вы вводите размер коробки N (1<=N<=25). Последующие 3*N строк содержат номера цветов раскраски коробки. Развертка коробки показана на рисунке. Первые N строк описывают раскраску верхней грани (в каждой N чисел), следующие N строк описывают переднюю, правую, заднюю и левую грани (в каждой 4*N чисел), затем N строк, описывающие нижнюю грань (в каждой N чисел). Все числа разделены пробелом. Номера цветов – натуральные числа, не превышающие N3. Программа выводит на экран искомое количество фрагментов.
Пример
Ввод
3
1 1 1
1 1 1
1 1 1
1 1 1 4 4 4 1 1 1 3 3 3
2 2 1 4 4 4 1 3 1 3 1 3
1 1 1 4 4 4 1 1 1 3 3 3
1 1 1
1 1 1
1 1 1
Вывод
6
|
