Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

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

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

Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. - C++
кому не трудно помогите сделать. если не трудно вам написать код. Дана прямоугольная таблица nxn клеток. В каждой клетке содержится...

Из каждой группы подряд идущих слов оставить только одну - C++
Пусть будет дан список слов. Из каждой группы подряд идущих слов оставить только одну.

Оставить в каждом слове текста с каждой последовательности идущих подряд одинаковых букв только одну букву - C++
Здравствуйте! Задание:Оставить в каждом слове текста с каждой последовательности идущих подряд одинаковых букв только одну букву. ...

Заполнить квадрат одинаковыми значениями по диагоналям - C++
На первой диагонали в квадрате расположены единицы, на второй диагонали – 2, на К – ой диагонали – к. Количество диагоналей у квадрата...

Как в одну строчечку структурку заполнить? - C++
struct sNumSave { int g_iOne; int g_iTwo; int g_iFree; } g_iNumData;

Собирание всех коней в одну клетку доски или количество коней, которые немогут прийти в даную клетку - Pascal
Может кто-то помочь срочно решить олимпиадную задачку. На шахматной доске размером NxM (2 ≤ N, M ≤ 100) находится Q (0 ≤ Q ≤ 10000)...

6
I.M.
566 / 549 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
19.08.2012, 15:47 #2
Можно ли поворачивать фигуры? Насколько разнообразны фигуры? Гарантировано ли то, что решение всегда есть? Или может получиться так, что фигур больше или меньше чем нужно.
0
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
19.08.2012, 15:57  [ТС] #3
фигуры поворачивать смысла нет. т.к. они - углы. фигуры нарисованы в 1 посте в начале. В задании написано, что если нельзя заполнить, то написать -1, значит решение негарантированно. фигур всего 4. Они просто повторяются. если так объяснять, то фигуры - это квадрат 2х2, где она клетка пустая (4 фигуры получается - все углы)
0
I.M.
566 / 549 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
19.08.2012, 16:09 #4
А количество тех или иных углов задано или можно брать сколько угодно?
0
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
19.08.2012, 16:12  [ТС] #5
Всего фигур должно быть (22n − 1) / 3. На счет отдельной фигуры не сказано (хоть двумя фигурами заполняй =) )
0
I.M.
566 / 549 / 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 с точкой решается тривиально

И дерево решений - явно не выход. Это же перебор.
1
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
19.08.2012, 16:23  [ТС] #7
Блин, гениально! Как я сам-то не додумался. Метод "разделяй и властвуй"... вот блин... Спасибо огромное!!
0
19.08.2012, 16:23
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.08.2012, 16:23
Привет! Вот еще темы с ответами:

Создать запись в клетку ссылки на другую клетку, запись в клетку функции суммирования блока клеток - C++ Builder
Ребят, подскажите- только начала изучать программу, создала таблицу, не получается создать запись в клетку ссылки на другую клетку, запись...

Заполнить каждую N-ю клетку в таблице (как по горизонтали, так и по вертикали) - VBA
Код присваивает значения ячейке: SH1.Cells(i1, j1).Value = dCp где i1=2, j1=11. Как мне сделать, чтобы в Excel таблице заполнились...

Шаг на одну клетку вперед и поворот влево/вправо (чередуя) на +/-Pi/2. Цена шага и поворота - один рубль. - Prolog
Задание:«Поиск оптимального пути движения робота R для перемещения деталей между станками A и В» на функциональном языке Prolog Шаг...

.NET 4.x Заполнить клетку животными и эмулировать бабуина, который берёт животных с наибольшей приятностью и гладит - C#
Условия задачи: У нас есть бабуины, коты, ежики и белки. Все они животные. У каждого животного есть имя, а еще параметр приятности,...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

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