eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Триомино

Триомино

\includegraphics{https://static.e-olymp.com/content/16/169089506fbd83f96bff0860ebe3f6899b2820ff.jpg} Фигуркой триомино называют связную фигуру, состоящую из трех квадратов. Существует всего два различных типа таких фигурок --- они изображены на рисунке. Все другие отличаются только поворотами. Прямоугольное поле размером \textbf{m }строк и \textbf{n} столбцов считается заполненным фигурками триомино, если: \begin{enumerate} \item Каждая фигурка находится в пределах поля и накрывает ровно три клетки. \item Фигурки не накладываются. \item Пустых (не покрытых фигуркой) клеток не более двух. \end{enumerate} Заполненное фигурками поле можно представить в виде прямоугольной таблицы. Значение \textbf{0} обозначает незаполненную клетку. Одинаковые натуральные значения обозначают, что клетки принадлежат одной фигурке, разные --- разным. Напишите программу, которая, проанализировав содержимое нескольких числовых двумерных таблиц, определит для каждой из них, задает ли она правильно заполненное фигурками триомино прямоугольное поле. \InputFile Первая строка содержит количество прямоугольных таблиц \textbf{t }(\textbf{2 }≤ \textbf{t }≤ \textbf{10}). Далее идет \textbf{t} блоков такой структуры. Первая строка блока содержит два целых числа \textbf{m} и \textbf{n }(\textbf{1 }≤ \textbf{m }≤\textbf{ 200}, \textbf{1 }≤ \textbf{n }≤ \textbf{200}) - количество строк и количество столбцов соответствующей таблицы. Далее идет \textbf{m }строк по \textbf{n }целых чисел в каждой. Значения этих чисел от \textbf{0} до \textbf{\[m×n/3\] }включительно. Размер входных данных не перевышает \textbf{512} Kb. \OutputFile Вывести \textbf{t }строк, в каждой - слово \textbf{YES} или слово \textbf{NO} (большими латинскими буквами) обозначающее, задает ли соответствующая таблица правильно заполненное фигурками триомино поле. \textit{\textbf{Прмечание}}: Рисунок к первому блоку: \includegraphics{https://static.e-olymp.com/content/50/507623121289267f102c09acfe80724c11321a9e.jpg}
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
2
4 8
1 2 2 2 6 7 7 9
1 4 4 3 6 7 8 9
1 0 4 3 6 8 8 9
10 10 10 3 0 5 5 5
2 6
1 1 2 2 1 1
0 1 0 2 0 1
Выходные данные #1
YES
NO
Автор Илья Порублёв
Источник 2012 XXV Всеукраинская олимпиада по информатике, Винница, Март 24 - 28, тур 1