Коридор Каир
Пентагональная плитка Каира представляет собой разбиение плоскости с использованием полуправильных пятиугольников. Такое название плитка получила потому что несколько улиц в Каире вымощены с использованием такого дизайна.
Рассмотрим конечную укладку, где каждый пятиугольник либо пустой (белый), либо заполненный (серый). Коридор - это максимальный набор пустых смежных пятиугольников, которые соединяют четыре границы плитки. Пятиугольники считаются смежными, если они имеют общую сторону, а не только угол. Нетрудно убедиться, что в каждой укладке может быть не более одного коридора. Говорят, что коридор минимален, если у него нет лишнего пятиугольника, то есть если какой-либо пятиугольник коридора заполнить, то набор оставшихся пятиугольников уже не будет коридором.
На рисунке вверху изображены четыре примера укладки плитки. В первых трех случаях имеется коридор, который выделен желтым цветом. Кроме того, коридоры (а) и (б) минимальны, но на рисунке (с) нет: например, плитки отмеченные символом Х, могут быть заполнены и коридор все еще будет существовать. В самой правой укладке нет коридора. Рисунки (а) и (с) соответствуют первому примеру.
Напишите программу, которая прочитает текстовые описания укладки плитки, и для каждого из них определит, существует ли коридор и является ли он минимальным. В последнем случае программа должна вычислить размер коридора, то есть количество пустых пентагональных плит в коридоре.
Входные данные
Первая строка содержит количество укладок t (1 ≤ t ≤ 10). Первая строка каждой укладки содержит два натуральных числа n[k] и m[k] (1 ≤ n[1] + n[2] + ... + n[t] ≤ 250 - общее число строк, 1 ≤ m[1] + m[2] + ... + m[t] ≤ 250 - общее число пар плиток). Каждая из следующих n[k] строк содержит 2 * m[k] цифр описывающих пары a[ij], b[ij] плит (0 - пусто и 1 - заполнено) в чередующемся горизонтальном / вертикальном порядке по шаблону "шахматной доски»" как показано на рисунке ниже.
Первая строка содержит количество укладок t (1 ≤ t ≤ 10). Первая строка каждой укладки содержит два натуральных числа n[k] и m[k] (1 ≤ n[1] + n[2] + ... + n[t] ≤ 250 - общее число строк, 1 ≤ m[1] + m[2] + ... + m[t] ≤ 250 - общее число пар плиток). Каждая из следующих n[k] строк содержит 2 * m[k] цифр описывающих пары a[ij], b[ij] плит (0 - пусто и 1 - заполнено) в чередующемся горизонтальном / вертикальном порядке по шаблону
Выходные данные
Выведите t строк; k-ая строка должна содержать размер коридора k-ой укладки если минимальный коридор существует, и NO MINIMAL CORRIDOR иначе.Пентагональная плитка Каира представляет собой разбиение плоскости с использованием полуправильных пятиугольников. Такое название плитка получила потому что несколько улиц в Каире вымощены с использованием такого дизайна.
Рассмотрим конечную укладку, где каждый пятиугольник либо пустой (белый), либо заполненный (серый). Коридор - это максимальный набор пустых смежных пятиугольников, которые соединяют четыре границы плитки. Пятиугольники считаются смежными, если они имеют общую сторону, а не только угол. Нетрудно убедиться, что в каждой укладке может быть не более одного коридора. Говорят, что коридор минимален, если у него нет лишнего пятиугольника, то есть если какой-либо пятиугольник коридора заполнить, то набор оставшихся пятиугольников уже не будет коридором.
На рисунке вверху изображены четыре примера укладки плитки. В первых трех случаях имеется коридор, который выделен желтым цветом. Кроме того, коридоры (а) и (б) минимальны, но на рисунке (с) нет: например, плитки отмеченные символом Х, могут быть заполнены и коридор все еще будет существовать. В самой правой укладке нет коридора. Рисунки (а) и (с) соответствуют первому примеру.
Напишите программу, которая прочитает текстовые описания укладки плитки, и для каждого из них определит, существует ли коридор и является ли он минимальным. В последнем случае программа должна вычислить размер коридора, то есть количество пустых пентагональных плит в коридоре.