Задача №3373. Печатная схема
Печатной схемой называется плоская поверхность содержащей узлы и перемычки, соединяющие пары узлов. Мы будем рассматривать печатные схемы специального вида, где все узлы расположены в узлах прямоугольной сетки, а перемычки (вертикальные или горизонтальные) соединяют пары соседних узлов. Печатная схема называется связной, если любые два узла соединены друг с другом последовательностью перемычек. На вход дается печатная схема, где некоторые соседние узлы уже соединены перемычками. К ней необходимо добавить некоторое количество перемычек таким образом, чтобы схема стала связной. Стоимость вертикальной перемычки – 1, а горизонтальной – 2.
Ваша программа должна по начальной печатной схеме определить количество добавляемых перемычек, минимальную стоимость такого добавления, а также вывести сами добавляемые перемычки.
Первая строка входного файла содержит два натуральных числа \(N\) и \(M\) – количество строк (\(1 \leq N \leq 100\)) и количество столбцов (\(1 \leq M \leq 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\)).
Первая строка должна содержать два числа \(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\)). Если решений несколько – выведите любое из них.
4 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 3 1 3 3 1 4 3 2 2 5 1