410151: GYM103965 E Очерк
Description
Художник Владимир, во время прогулки по осеннему саду, наблюдая за тем как огненно-рыжие листья падают с деревьев на поверхность сверкающих на солнце лужиц, и слушая пение птиц, которые уже совсем скоро покинут родные края, совершенно забыл, что ему завтра нужно сдавать проект.
Второпях Владимир нашёл какой-то компьютер, на котором он решил воссоздать набросок, который у нашего художника был в голове с точностью до пикселя. Вот только графический редактор, которым он решил воспользоваться, был крайне ограничен.
В этом графическом редакторе есть только две кисти — одна в форме крестика, другая в виде нолика. Можно выбрать какую-то клетку $$$(x, y)$$$ ($$$1 \leqslant x \leqslant n$$$; $$$1 \leqslant y \leqslant m$$$) и одну из двух кистей. Тогда если была выбрана кисть-нолик, то будут покрашены в красный все клетки, у которых есть общая сторона с выбранной клеткой. Если же выбран крестик, то красными станут выбранная клетка и все, соседние с ней по углу.
Вам даётся набросок размера $$$n \times m$$$. Определите, может ли Владимир воссоздать его, используя только эти две кисти. Разрешается частью кисти выходить за границу рисунка.
Входные данныеВ первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$m$$$ — размеры рисунка ($$$1 \leqslant n, m \leqslant 1000$$$).
В следующих $$$n$$$ строках вводится по $$$m$$$ символов — символ равен «*», если пиксель покрашен в красный, и «.», если пиксель покрашен в белый.
Выходные данныеВыведите ответ на задачу — «YES» (без кавычек), если можно воссоздать рисунок, и «NO» в противном случае.
ПримерыВходные данные5 5 ..... ..*** ..*** ..*** .....Выходные данные
YESВходные данные
5 5 ..... ..... *.... .*... *.*..Выходные данные
YESПримечание
В первом тесте можем сделать два «мазка» в клетке $$$(3;4)$$$ — один крестик, другой нолик.
Во втором тесте достаточно поставить нолик в клетке $$$(4;1)$$$ и в клетке $$$(5; 2)$$$. Разрешается кистью выходить за границы рисунка.