Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ 1 сообщение ] |
|
Автор | Сообщение | |
---|---|---|
Fireman |
|
|
Дико извиняюсь с выбором темы, но не могу понять куда с ней. Есть следующая задача: Имеется прямоугольное клеточное поле размером [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 делится с остатком на кол-во клеток фигуры - значить наложить принципиально нельзя, иначе - надо проверить Вопрос: существует ли решение, существенно оптимальнее перебора |
||
Вернуться к началу | ||
[ 1 сообщение ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Задачи о расположении людей и билетах
в форуме Теория вероятностей |
0 |
324 |
22 мар 2017, 16:33 |
|
Задача на фигуры и цвет
в форуме Комбинаторика и Теория вероятностей |
1 |
508 |
31 май 2015, 11:46 |
|
Задача о прохождении фигуры(?) | 0 |
219 |
26 июн 2016, 19:03 |
|
Задача - расчет параметров фигуры-шар | 6 |
467 |
09 окт 2017, 15:50 |
|
Поле
в форуме Дифференциальное исчисление |
2 |
77 |
07 янв 2024, 11:17 |
|
Векторное поле
в форуме Векторный анализ и Теория поля |
2 |
144 |
05 май 2023, 14:10 |
|
Результирующее поле
в форуме Электричество и Магнетизм |
0 |
213 |
16 май 2021, 15:36 |
|
Электростатическое поле
в форуме Электричество и Магнетизм |
1 |
342 |
03 июн 2015, 10:54 |
|
Скалярное поле
в форуме Векторный анализ и Теория поля |
3 |
1515 |
17 май 2014, 13:26 |
|
Электрическое поле
в форуме Электричество и Магнетизм |
0 |
378 |
04 июн 2015, 12:34 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |