2j-two-rectangles.js

/*

J. Два прямоугольника

Ограничение времени	1 секунда (фактическое использование на тестах – до 92ms)
Ограничение памяти	64Mb (фактическое использование на тестах – до 10.61Mb)
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Недавно один известный художник-абстракционист произвел на свет новый шедевр — картину «Два черных непересекающихся прямоугольника». Картина представляет собой прямоугольник m× n, разбитый на квадраты 1×1, некоторые из которых закрашены любимым цветом автора — черным. Федя — не любитель абстрактных картин, однако ему стало интересно, действительно ли на картине изображены два непересекающихся прямоугольника. Помогите ему это узнать. Прямоугольники не пересекаются в том смысле, что они не имеют общих клеток.

Формат ввода
Первая строка входного файла содержит числа m и n (1 ≤ m, n ≤ 200). Следующие m строк содержат описание рисунка. Каждая строка содержит ровно n символов. Символ «.» обозначает пустой квадрат, а символ «#» — закрашенный.

Формат вывода
Если рисунок можно представить как два непересекающихся прямоугольника, выведите в первой строке «YES», а в следующих m строках выведите рисунок в том же виде, в каком он задан во входном файле, заменив квадраты, соответствующие первому прямоугольнику на символ «a», а второму — на символ «b». Если решений несколько, выведите любое.

Если же этого сделать нельзя, выведите в выходной файл «NO».

Пример 1

Ввод
2 1
#
.

Вывод
NO

Пример 2

Ввод
2 2
..
##

Вывод
YES
..
ab

Пример 3

Ввод
1 3
###

Вывод
YES
abb

Пример 4

Ввод
1 5
####.

Вывод
YES
abbb.

*/

const fs = require('fs');

const input = fs.readFileSync('input.txt', 'utf8').toString().trim().split('\n');

const [height, width] = input[0].trim().split(' ').map((value) => parseInt(value));

const picture = new Array(height).fill(0).map(() => new Array(width).fill('.'));

let startY = -1;
let startX = -1;

for (let h = 1; h < input.length; ++h) {
    const row = input[h].trim();
    for (let w = 0; w < width; ++w) {
        if (row[w] === '#') {
            picture[h - 1][w] = '#';

            if (startY === -1) {
                startY = h - 1;
                startX = w;
            }
        }
    }
}

let hasSolution = true;
let firstRectPainted = false;
let firstRectPosX = 0;
let firstRectPosY = 0;
let firstRectWidth = 0;
let firstRectHeight = 0;
let secondRectPainted = false;
let secondRectWidth = 0;

mainLoop:
for (let globalY = 0; globalY < height; ++globalY) {
    for (let globalX = 0; globalX < width; ++globalX) {
        if (picture[globalY][globalX] === '#') {
            let localRectWidth = 0;
            for (let localX = globalX; localX < width; ++localX) {
                if (picture[globalY][localX] === '#') {
                    ++localRectWidth;
                    if (!firstRectPainted) {
                        ++firstRectWidth;
                        picture[globalY][localX] = 'a';
                    } else if (!secondRectPainted) {
                        ++secondRectWidth;
                        picture[globalY][localX] = 'b';
                    } else {
                        hasSolution = false;
                        break mainLoop;
                    }
                } else {
                    break;
                }
            }

            if (!firstRectPainted) {
                firstRectPosY = globalY;
                firstRectPosX = globalX;
                ++firstRectHeight;
            }

            linesLoop:
            for (let localY = globalY + 1; localY < height; ++localY) {
                const line = picture[localY].slice(globalX, globalX + localRectWidth);
                for (const value of line) {
                    if (value !== '#') {
                        break linesLoop;
                    }
                }

                if (globalX > 0 && picture[localY][globalX - 1] === '#' &&
                    globalX + localRectWidth < width && picture[localY][globalX + localRectWidth] === '#') {
                        break linesLoop;
                }

                for (let localX = globalX; localX < globalX + localRectWidth; ++localX) {
                    if (!firstRectPainted) {
                        picture[localY][localX] = 'a';
                    } else if (!secondRectPainted) {
                        picture[localY][localX] = 'b';
                    }
                }

                if (!firstRectPainted) {
                    ++firstRectHeight;
                }
            }

            if (!firstRectPainted) {
                firstRectPainted = true;
            } else if (!secondRectPainted) {
                secondRectPainted = true;
            }
        }
    }
}

if (firstRectWidth !== 0) {
    firstRectPainted = true;
}

if (secondRectWidth !== 0) {
    secondRectPainted = true;
}

if (hasSolution) {
    if (!firstRectPainted) {
        hasSolution = false;
    } else if (!secondRectPainted) {
        if (firstRectWidth === 1 && firstRectHeight === 1) {
            hasSolution = false;
        } else if (firstRectHeight === 1) {
            picture[firstRectPosY][firstRectPosX + firstRectWidth - 1] = 'b';
            secondRectPainted = true;
        } else if (firstRectHeight !== 1) {
            for (let localX = firstRectPosX; localX < firstRectPosX + firstRectWidth; ++localX) {
                picture[firstRectPosY + firstRectHeight - 1][localX] = 'b';
            }
            secondRectPainted = true;
        }
    }
}

let result = hasSolution ? 'YES' : 'NO';

if (hasSolution) {
    result += '\n' + picture.map((arr) => arr.join('')).join('\n')
}

fs.writeFileSync('output.txt', `${result}`);