Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 5.00
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
#1

Заполнить квадрат углами и оставить одну пустую клетку - C++

19.08.2012, 15:26. Просмотров 1305. Ответов 6
Метки нет (Все метки)

Привет всем! Суть задачи такова: есть фигуры
11_22_3___4
1___2_33_44
И дан квадрат 2n x 2n
Также есть координаты точки, которая должна остаться пустой.
Суть такова: нужно заполнить этот квадрат фигурами выше и чтоб эта клетка осталась пустой.

Натолкните хотя бы на мысль, как сгенерировать это все!!
Я попробовал несколько вариантов: заполнить почти все прямоугольниками 2х3, а то место, где должна быть точка, оставить и его как-нить заполнить. Но там есть исключения, когда точка стоит не так, как надо, приходится заполнять по-другому, вобщем куча условий и ваще некруто.
Затем думал как-нибудь заполнить все поле и оставить в центре одну пустую точку, затем нужную точку поставить в нужное место и уже исправлять то, что сделалось неправильно! Но там тоже куча проблем.
Вобщем, дайте мне совет, как можно это генерировать!!!

Добавлено через 1 час 40 минут
Есть конечно еще одна идея. Сделать дерево всевозможных решений. Но мне кажется, что дерево для квадрата 512х512 будет слишком большим. Может быть в этой степи мне подскажете, как сделать грамотное дерево?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.08.2012, 15:26     Заполнить квадрат углами и оставить одну пустую клетку
Посмотрите здесь:

C++ Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку.
Из каждой группы подряд идущих слов оставить только одну C++
C++ Может ли шахматный конь перейти в указанную клетку доски?
Класс «Квадрат»: можно ли вписать в объект-квадрат со стороной A окружность радиуса R C++
Создать класс Angle для работы с углами C++
C++ Оставить в каждом слове текста с каждой последовательности идущих подряд одинаковых букв только одну букву
C++ Как в одну строчечку структурку заполнить?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
19.08.2012, 15:47     Заполнить квадрат углами и оставить одну пустую клетку #2
Можно ли поворачивать фигуры? Насколько разнообразны фигуры? Гарантировано ли то, что решение всегда есть? Или может получиться так, что фигур больше или меньше чем нужно.
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
19.08.2012, 15:57  [ТС]     Заполнить квадрат углами и оставить одну пустую клетку #3
фигуры поворачивать смысла нет. т.к. они - углы. фигуры нарисованы в 1 посте в начале. В задании написано, что если нельзя заполнить, то написать -1, значит решение негарантированно. фигур всего 4. Они просто повторяются. если так объяснять, то фигуры - это квадрат 2х2, где она клетка пустая (4 фигуры получается - все углы)
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
19.08.2012, 16:09     Заполнить квадрат углами и оставить одну пустую клетку #4
А количество тех или иных углов задано или можно брать сколько угодно?
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
19.08.2012, 16:12  [ТС]     Заполнить квадрат углами и оставить одну пустую клетку #5
Всего фигур должно быть (22n − 1) / 3. На счет отдельной фигуры не сказано (хоть двумя фигурами заполняй =) )
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
19.08.2012, 16:17     Заполнить квадрат углами и оставить одну пустую клетку #6
Идея такая (несколько сумбурно):
1. разбиваем квадрат на 4 равных квадрата
2. определяем в каком из них лежит пустая точка
3. вначале работаем с теми тремя квадратами, в которых точки нет
3.1 ставим в одном углу каждого из трех квадратов якобы пустую точку так, чтобы эти три пустых точки образовывали уголок
3.2 таким образом получаем, что все 4 квадрата имеют по пустой точке
4. теперь к каждому квадрату с точкой надо применять пункт 1. до тех пор, пока не дойдем до квадрата 2х2 с точкой
5. квадрат 2х2 с точкой решается тривиально

И дерево решений - явно не выход. Это же перебор.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.08.2012, 16:23     Заполнить квадрат углами и оставить одну пустую клетку
Еще ссылки по теме:

Вычислить площадь треугольника со сторонами k и прилежащими углами a и b C++
C++ Заполнить квадрат одинаковыми значениями по диагоналям
Определить, бьет ли ферзь, находящийся в клетке (xy, y1) клетку (x2, y2) C++
C++ Вывести квадрат большего числа и квадрат меньшего
Количество обходов шахматной доски конём (с возвратом в начальную клетку) C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
19.08.2012, 16:23  [ТС]     Заполнить квадрат углами и оставить одну пустую клетку #7
Блин, гениально! Как я сам-то не додумался. Метод "разделяй и властвуй"... вот блин... Спасибо огромное!!
Yandex
Объявления
19.08.2012, 16:23     Заполнить квадрат углами и оставить одну пустую клетку
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru