Разбор добавил Александр Чистяков
Если немного посидеть и попытаться разными способами прикладывать два прямоугольника друг к другу,
можно заметить следующий очень полезный факт: как минимум у одного из этих прямоугольников два
диаметральных угла будут выделяться, образовывая внешние углы получившейся при совмещении фигуры.
Поэтому, один раз пробежавшись по матрице и запомнив координаты чёрных клеток, имеющих не более двух
закрашенных соседей, можно определить все клетки, способные являться двумя диаметральными вершинами
одного из прямоугольников.
Для первого теста из условия это клетки: (1,2),(1,4),(2,2),(3,4),(3,5).
Два очевидных частных случая для отсечения:
1) Если всего у нарисованной фигуры более 8 внешних углов, то она явно не могла быть получена путём
совмещения 2х прямоугольников.
2) Если оказалось, что такая клетка всего одна, то нарисован только 1 прямоугольничек 1*1 и его тоже
нельзя получить из 2х непересекающихся фигур.
Во всех остальных случаях следует попытаться поискать описанную пару диагональных вершин. Для этого
переберём все пары вершин из полученного списка (всего не более 8*8 = 64 вариантов). Для каждой пары:
Во-первых, проверим, что часть плоскости, которую вершины из пары ограничивают полностью закрашена.
Во-вторых, проверим: образуют ли оставшиеся вне прямоугольника клетки полностью закрашенный
прямоугольник.
Если хотя бы для одной пары оба условия выполнились, то красим картину в соответствии с найденными
парами и выводим ответ.
Если такой пары не нашли, выводим "NO".
Общее количество действий заведомо не превысит 8^2 * 200^2 * C (для каждой пары нам придётся один
или несколько раз (в зависимости от метода проверки на закрашенность) пробежаться по всей матрице
для поиска второго прямоугольника).
На прямоугольном поле есть закрашенные и незакрашенные клетки. Требуется определить, можно ли разбить закрашенные клетки на два прямоугольника, со сторонами, параллельными осям координат.
Недавно один известный художник-абстракционист произвел на свет новый шедевр – картину «Два черных непересекающихся прямоугольника». Картина представляет собой прямоугольник \(m\)×\(n\), разбитый на квадраты 1×1, некоторые из которых закрашены любимым цветом автора – черным. Федя – не любитель абстрактных картин, однако ему стало интересно, действительно ли на картине изображены два непересекающихся прямоугольника. Помогите ему это узнать. Прямоугольники не пересекаются в том смысле, что они не имеют общих клеток.
Выходные данные
Если рисунок можно представить как два непересекающихся прямоугольника, выведите в первой строке «YES», а в следующих m строках выведите рисунок в том же виде, в каком он задан во входном файле, заменив квадраты, соответствующие первому прямоугольнику на символ «a», а второму – на символ «b». Если решений несколько, выведите любое.
Если же этого сделать нельзя, выведите в выходной файл «NO».