Эта задача на сайте acmp.ru с самого начала его существования, но четыре года назад были добавлены тесты (по сути, один особый случай), и почти все решения получили Wrong answer. Давайте разбираться.
Важным моментом является то, что нам гарантируют, что положение прямоугольников можно однозначно определить. Это означает, что у каждого прямоугольника виден кусочек каждой из его сторон. Ведь если полностью покрыть какую-нибудь сторону, то не будет понятно, где именно она проходит.
Таким образом получаем, что в этой задаче надо для каждого числа из входной таблицы найти пределы её встречаемости: самую нижнюю строку, самую верхнюю строку и, аналогично, со столбцами.
Ограничения в задаче не очень сильные, поэтому можно решать на любом языке. Давайте посмотрим, как это будет выглядеть на Python.
Считаем данные и инициализируем границы прямоугольников предельными значениями, чтобы потом можно было их релаксировать. Обратим внимание, что, чтобы не переживать про нумерацию прямоугольников с 1, размеры массивов на единицу больше. К тому же, нулевой элемент нам тоже пригодится.
Напишем функцию, которая "растягивает" границы прямоугольника ind до координаты (x, y), если она ещё им не покрывается.
Теперь можно считывать все остальные данные и сразу обновлять границы прямоугольников:
Цикл по y идёт с n - 1 до 0 (включительно), чтобы не заморачиваться потом с переводом в декартовы координаты.
Во вложенном цикле мы пропускаем все нули, тогда получается, что в точке (x, y) находится прямоугольник a, и вызываем обновление его границ. Ещё мы каждый раз обновляем нулевой прямоугольник. Таким образом получается, что в нулевом элементе будут лежать границы прямоугольника, покрывающего все остальные.
Пора раскрыть секрет 14-го теста. Он заключается в том, что на самом деле прямоугольник (или несколько) может быть полностью закрыт. Но такое возможно лишь в одном случае - когда накрывающий их прямоугольник размера 1х1 и он единственный из видимых. Действительно, если на всём поле закрыта лишь одна клетка, то очевидно, что все прямоугольники расположены в ней.
Тогда вывод результата будет иметь два случая, если прямоугольник видим, то выводим его границы, если нет, то - глобальную область покрытия.
Предыдущий выпуск: Задача 474. Последовательность Кеане
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
