— A я никогда больше больше не буду рисовать, — ответил Незнайка, —
Рисуешь, рисуешь, а никто даже спасибо не скажет, все только ругаются.
Великий художник-абстракционист Герман Брукс придумал новый стиль в
живописи — бактографию. И что же это за стиль, спросите вы. А все очень просто:
теперь каждая картина — живая, в буквальном смысле этого слова.
Герман рисует бактериями.
Такая картина — настоящее произведение искусства. Видели бы вы
это завораживающее зрелище, переливающееся двумя, а то и тремя сотнями разных оттенков.
Но как же показать это чудо простым людям? Фотография или видео просто неспособны
передать всю гамму красок, а музея у Германа пока еще нет (не нравятся новаторские
идеи современным хранителям культуры, куда уж с ними спорить).
К тому же подробно рисунок можно рассмотреть только под микроскопом.
В конце концов было решено скопировать несколько особо удачных картин в
тысячах экземпляров и продавать в качестве сувениров.
Однако возникла проблема. Сам Герман, как настоящий творец, копировать не желает,
а биоинженеры, нанятые Германом, в один голос заявляют, что можно сделать копию, только если знать
четкую последовательность, в которой полотно заселяли бактериями.
Ваша задача — восстановить эту последовательность.
Для решения этой задачи биоинженеры сообщили следующую информацию:
- Законченная картина представляет собой прямоугольный холст,
разделенный на одинаковые квадратные клетки, каждая из которых заселена
несколькими бактериями.
- Перед рисованием холст обязательно дезинфицируется, все его клетки
пусты и не содержат бактерий.
- В каждой клетке холста может быть не более четырех бактерий.
- Процесс рисования заключается в том, что биоинженеры поочередно
селят в свободные клетки холста по одной бактерии, при этом в каждой из
соседних заселенных клеток (сверху, снизу, справа, слева) количество
бактерий увеличивается на одну. Если в некоторой клетке стало 5 бактерий,
то из-за перенаселения 4 из них погибают.
- Поселить бактерию в уже заселенную клетку невозможно, ибо это приводит
к непредсказуемой цепной реакции, портящей все полотно.
Исходные данные
Первая строка содержит числа n и m — размеры картины Германа
(1 ≤ n, m ≤ 20).
Далее описывается сама картина в виде таблицы из n строк
по m чисел, где в каждой ячейке записано количество бактерий
в соответствующей клетке картины — целое число от 1 до 4.
Результат
В случае если получить исходную картину процедурой, доступной биоинженерам,
невозможно, вывести единственное слово «No».
Если же вам удалось найти какую-либо последовательность, позволяющую создать
копию шедевра Германа, то выведите в первой строке «Yes»,
а в следующих строках саму последовательность: по два числа в каждой строке
— номер строки и номер стоблца заселяемой клетки картины.
Пример
исходные данные | результат |
---|
3 3
2 2 1
3 1 3
1 2 2
| Yes
2 2
2 1
1 1
1 2
2 3
1 3
3 3
3 2
3 1
|
Автор задачи: Евгений Крохалев
Источник задачи: NEERC 2008, Четвертьфинал Восточного подрегиона