На какое наименьшее число прямоугольников можно расчертить лист

@catauggie · Регистрация: 20.09.2018

Студворк — интернет-сервис помощи студентам

Перед Женей лежит белый лист размера N х М клеток. Часть клеток Женя закрасила синим, а оставшуюся часть она хочет расчертить на прямоугольники. Прямоугольник должен содержать только белые клетки, грани прямоугольника проходят по граням клеток. На какое наименьшее число прямоугольников она может расчертить свой лист?
Первая строка содержит N>=1 и М<=12. Следующие N строк содержат
no M чисел в каждой: 1 если клетка синяя, 0 если белая
Вывести одно число: минимальное число прямоугольников.

Мне из условия не совсем понятно, считать ли одну белую клетку за прямоугольник, поэтому я решил что они тоже подойдут.
Фактически, надо подсчитать число клеток с 0 и если соседние клетки с 0 имеет общую грань, то их считать за один прямоугольник.

На какое наименьшее число прямоугольников можно расчертить лист

Мое решение выглядит как-то так:

Python
1
2
3
4
5
6
7
8
9
N = int(iput())
M = int(iput())
sroki = range(N)
for i in sroki:
    x = int(input()) // ввод значения 0 или 1
prg = 0 //начально число прямоугоьников
if x[i]=x[i+1]:
    prg +=1
print(prg)

Но как вводить именно для каждой строки M раз значения x я не знаю. Помогите, пожалуйста, исправить. Заранее большое спасибо_))

@dondublon · 21.06.2019, 16:24

Одну клетку считать, почему нет?
Задача не такая простая, как вам кажется. На сколько прямоугольников ваш алгоритм разобьёт следующую фигуру?

Code
1
2
3
. X .
X X X
X X X

Правильный ответ - 2.

Добавлено через 4 минуты
Похоже, решается жадным алгоритмом.

@Semen-Semenich · 21.06.2019, 16:32

Сообщение от dondublon

Правильный ответ - 2.

а по мне так 3 если брать по вертикали то первый прямоугольник это 2 икса первого столбика потом 3 второго и опять 2 третьего. не сказано же что прямоугольники должны быть равны

@dondublon · 21.06.2019, 17:13

Semen-Semenich, надо ж наименьшее число.
Тогда два - верхний 1*1 и нижний 3*2.

Рыжий Лис · 21.06.2019, 18:23

Python
1
2
3
4
5
6
7
8
9
n, m = input().split(' ')
n = int(n)
m = int(m)
 
arr = []
for _ in range(n):
    arr.append(input().split(' '))
 
print(arr)

Code
1
2
3
4
2 3
1 0 1
1 0 1
[['1', '0', '1'], ['1', '0', '1']]

@Semen-Semenich · 21.06.2019, 18:33

dondublon, упустил что наименьшее количество

Сообщение от dondublon

Тогда два - верхний 1*1 и нижний 3*2

ну 1*1 это клетка квадрат а не прямоугольник. тогда один, откинув верхний не закрашенный квадрат
.х.
и оставив один большой прямоугольник 3*2
ххх
ххх

@dondublon · 21.06.2019, 18:45

Semen-Semenich, 1*1 - это маленький прямоугольник. Квадрат, кстати, тоже прямоугольник

Откидывать его мы не имеем права, это минус один прямоугольник получается.

@catauggie · 21.06.2019, 20:28 **[ТС]**

а можно тогда реализовать алгоритм следующим образом:
1) проверять все соседние четыре квадрата, если данный квадрат находится не у края

Python
1
2
if x [i,j]==x[i+1,j] or x [i,j]==x[i,j+1] or x [i,j]==x[i-1,j] or x [i,j]==x[i,j-1] :
     prg +=1

2) если у края, то использовать другой подход

При этом надо как-то соотнести m и n с i и j

@dondublon · 24.06.2019, 11:07

catauggie, думаю, проверять соседние 4 смысла нет.
Жадный алгоритм (посмотрите, что это).
Идём сверху вниз и слева направо. Это не строго, просто для определённости.
Берём верхние точки нашей фигуры, их них - левую.
От этой точки идём вправо, пока можем (т.е. пока непрерывный ряд точек не закончится). Получили верхнюю сторону прямоугольника.
Теперь идём вниз этой стороной, тоже пока можем. Тут чуток сложнее, т. к. надо просмотреть все точки в ряду, а не одну.
Как упёрлись - всё, получили очередной прямоугольник, его "вычитаем" из фигуры. Кстати, делить всё изображение на фигуры необязательно.
Ну и всё, повторяем, пока есть нерассмотреные точки.
Если есть возможность - используйте numpy, будет меньше кода.

@catauggie · 24.06.2019, 17:08 **[ТС]**

dondublon , а как это реализовать в Python? Про жадный алгоритм я слышал, но как применить на практике не знаю.

@dondublon · 24.06.2019, 17:26

Что именно реализовать? Всю программу? Я редко пишу готовые программы.
Алгоритм-то понятен? Могу сделать поясняющий рисунок, если нет.
Давайте вы начнёте, будут какие-то конкретные вопросы - спрашивайте.

@catauggie · 24.06.2019, 20:04 **[ТС]**

я просто не знаю как написать жадный алгоритм на питоне. если бы какие-нибудь материалы понятные прочесть

@dondublon · 25.06.2019, 10:11

catauggie, жадный алгоритм - это не какой-то конкретный алгоритм, это просто довольно общий способ решения задач, когда на каждой итерации берём по максимуму для нашего решения, без особых раздумий, как в ДП.

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия SDL 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual. . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	21.06.2019, 17:13
	Semen-Semenich, надо ж наименьшее число. Тогда два - верхний 11 и нижний 32. 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	21.06.2019, 18:45
	Semen-Semenich, 1*1 - это маленький прямоугольник. Квадрат, кстати, тоже прямоугольник Откидывать его мы не имеем права, это минус один прямоугольник получается. 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	24.06.2019, 11:07
	catauggie, думаю, проверять соседние 4 смысла нет. Жадный алгоритм (посмотрите, что это). Идём сверху вниз и слева направо. Это не строго, просто для определённости. Берём верхние точки нашей фигуры, их них - левую. От этой точки идём вправо, пока можем (т.е. пока непрерывный ряд точек не закончится). Получили верхнюю сторону прямоугольника. Теперь идём вниз этой стороной, тоже пока можем. Тут чуток сложнее, т. к. надо просмотреть все точки в ряду, а не одну. Как упёрлись - всё, получили очередной прямоугольник, его "вычитаем" из фигуры. Кстати, делить всё изображение на фигуры необязательно. Ну и всё, повторяем, пока есть нерассмотреные точки. Если есть возможность - используйте numpy, будет меньше кода. 0

@catauggie 24 / 5 / 0 Регистрация: 20.09.2018 Сообщений: 310
	24.06.2019, 17:08 [ТС]
	dondublon , а как это реализовать в Python? Про жадный алгоритм я слышал, но как применить на практике не знаю. 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	24.06.2019, 17:26
	Что именно реализовать? Всю программу? Я редко пишу готовые программы. Алгоритм-то понятен? Могу сделать поясняющий рисунок, если нет. Давайте вы начнёте, будут какие-то конкретные вопросы - спрашивайте. 0

@catauggie 24 / 5 / 0 Регистрация: 20.09.2018 Сообщений: 310
	24.06.2019, 20:04 [ТС]
	я просто не знаю как написать жадный алгоритм на питоне. если бы какие-нибудь материалы понятные прочесть 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	25.06.2019, 10:11
	catauggie, жадный алгоритм - это не какой-то конкретный алгоритм, это просто довольно общий способ решения задач, когда на каждой итерации берём по максимуму для нашего решения, без особых раздумий, как в ДП. 0