Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Печатная схема

(Время: 1 сек. Память: 16 Мб Сложность: 75%)

Печатной схемой называется плоская поверхность содержащей узлы и перемычки, соединяющие пары узлов. Мы будем рассматривать печатные схемы специального вида, где все узлы расположены в узлах прямоугольной сетки, а перемычки (вертикальные или горизонтальные) соединяют пары соседних узлов. Печатная схема называется связной, если любые два узла соединены друг с другом последовательностью перемычек. На вход дается печатная схема, где некоторые соседние узлы уже соединены перемычками. К ней необходимо добавить некоторое количество перемычек таким образом, чтобы схема стала связной. Стоимость вертикальной перемычки – 1, а горизонтальной – 2.

Ваша программа должна по начальной печатной схеме определить количество добавляемых перемычек, минимальную стоимость такого добавления, а также вывести сами добавляемые перемычки.

Входные данные

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество строк и количество столбцов соответственно (1 ≤ N, M ≤ 100). Каждый узел определяется своими координатами, нумерация начинается с верхнего левого угла (координаты (1, 1)). Далее дается описание решетки в виде N строк по M чисел. Каждое число обозначает связь узла (i, j) с узлами (i+1, j) и (i, j+1) в следующем формате:

0 – узел (i, j) не соединен ни с одним из узлов (i+1, j) и (i, j+1)

1 – узел (i, j) соединен только с узлом (i+1, j)

2 – узел (i, j) соединен только с узлом (i, j+1)

3 – узел (i, j) соединен и с узлом (i+1, j), и с узлом (i, j+1).

Выходные данные

Первая строка выходного файла OUTPUT.TXT должна содержать два числа K и V – количество добавленных перемычек и стоимость добавления соответственно. Каждая из следующих K строк должна содержать описание добавленной перемычки в формате i, j, d, где (i, j) – координаты начального узла, а d может принимать значения 1 или 2. d=1 обозначает, что соединены узлы (i, j) и (i+1, j), d=2 – узлы (i, j) и (i, j+1). Если решений несколько – выведите любое из них.

Пример

INPUT.TXTOUTPUT.TXT
14 5
2 1 1 2 1
0 3 0 1 0
3 0 0 3 1
0 2 0 2 0
5 6
1 1 1
2 5 1
3 2 1
3 3 1
3 3 2

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Получи дерево
 B. Минимальный каркас
 C. Связанное множество
 D. Остовное дерево
 E. Школы
 F. Печатная схема

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru