Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Задача о расположении/наложении фигуры на поле
СообщениеДобавлено: 30 июл 2018, 21:19 
Не в сети
Одарённый
Зарегистрирован:
20 дек 2016, 11:08
Сообщений: 153
Cпасибо сказано: 2
Спасибо получено:
6 раз в 5 сообщениях
Очков репутации: -3

Добавить очки репутацииУменьшить очки репутации
Приветствую

Дико извиняюсь с выбором темы, но не могу понять куда с ней.

Есть следующая задача:

Имеется прямоугольное клеточное поле размером [math]w \times h[/math].
В каждой клетке поля содержится значение или 0 (пусто) или 1 (занято).
Есть фигурка, состоящая из n элементов, занимающее место [math]a \times b[/math].

Необходимо определить, можно ли эту фигурку (без поворотов и отражений, т.е. самый простой вариант) положить на клеточном поле так, чтобы клетки фигурки (1) легли только в свободные клетки поля (0).

Например, клеточное поле выглядит так:

00111010001
11010011110
00011001100

а фигурка так:

01
11
01


Решения:

Самое простое решение - пробежаться по всему клеточному полю (вернее практически по всему - [math]w - a + 1 \times h - b + 1[/math]) и проверить, а удачно ли накладывается фигура.
Но такой подход займёт времени [math]O(n \times (w - a + 1) \times (h - b + 1))[/math] времени.
Конечно с чисто теоретически после первой неудачной клетки проверку можно закончить и переходить к следующим координатам, но практически все таки быстрее сначала проверить всё (например, подсчитать кол-во пустых клеток) и лишь потом делать выводы

Более сложное решение - проверять сколько всего пустых клеток есть и если их меньше n - принимать решение, что наложить фигуру гарантированно невозможно.

Но есть ли еще более оптимальные решения?
Какой-нибудь инвариант поля, который если фигура может быть наложена меняться не будет?

Если бы вопрос стоял так: есть места ровно под 1 фигуру, то такая задача решается легко:
1) каждой клетке присваивается индивидуальный номер (1,2,3,4,5,6,7...)
2) вычисляется сумма всех номеров пустых клеток X
3) для фигуры вычисляется сумма всех номеров занятых клеток Y (из рассчёта, если бы фигура была наложена по координате 1,1)
4) если X - Y делится с остатком на кол-во клеток фигуры - значить наложить принципиально нельзя, иначе - надо проверить


Вопрос: существует ли решение, существенно оптимальнее перебора

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ 1 сообщение ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задачи о расположении людей и билетах

в форуме Теория вероятностей

Dasha8547

0

324

22 мар 2017, 16:33

Задача на фигуры и цвет

в форуме Комбинаторика и Теория вероятностей

studenenter

1

508

31 май 2015, 11:46

Задача о прохождении фигуры(?)

в форуме Дискретная математика, Теория множеств и Логика

Interesno

0

219

26 июн 2016, 19:03

Задача - расчет параметров фигуры-шар

в форуме Аналитическая геометрия и Векторная алгебра

antronset

6

467

09 окт 2017, 15:50

Поле

в форуме Дифференциальное исчисление

Lfed

2

77

07 янв 2024, 11:17

Векторное поле

в форуме Векторный анализ и Теория поля

Fershtein_69

2

144

05 май 2023, 14:10

Результирующее поле

в форуме Электричество и Магнетизм

Kaori

0

213

16 май 2021, 15:36

Электростатическое поле

в форуме Электричество и Магнетизм

Zed

1

342

03 июн 2015, 10:54

Скалярное поле

в форуме Векторный анализ и Теория поля

Isabella

3

1515

17 май 2014, 13:26

Электрическое поле

в форуме Электричество и Магнетизм

Zed

0

378

04 июн 2015, 12:34


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved