 |
|
Модераторы: Poseidon |
 
|
|
[Алгоритм] Вычисление прямоугольников. Типа говоломка :) 
| Ak47black |
|
|||
 Эксперт  Профиль Группа: Завсегдатай Сообщений: 2205 Регистрация: 2.12.2005 Репутация: нет Всего: 0 |
Здравствуйте.
Пишу в этом разделе так как моя проблема чемто напоминает головоломку.  Вообщем может есть люди кто любит чтото такое решать или просто могут помочь.  Скока не пробовал решить, ну не получается ни как, невсё как надо высчитывается, какието теряются. Попробую описать проблему как можно чётче. Значит есть файл размером (Высота разрешения экрана)*(Длинна разрешения экрана) байт. В этом файле хранится так мной называемая маска изменений, эта маска представляет из себя массив байт, каждый байт отвечает за то - было-ли изменение пикселя. FFh соотвествует изминённому байту, а 00h не изминённому. Чтобы определить был ли пиксель который находиться по (X,Y) изминён я использую следущую формулу -
Нус попробую нарисовать что я тут говорю визуально (содержимое файла динамически меняется)  Задача сделать функцию которая высчитывала-бы из этой 'маски изменений' прямоугольники изменений. Тоесть есть надо получить координаты прямоугольников внутри которых произошли изменения. Требования
 Код можете выкладывать на любом языке программирования, главное чтобы он отражал мысль решения этой проблемы. Если что-то не чётко написал то извиняюсь, напишите что имеено поясню поконкретней. Это сообщение отредактировал(а) Ak47black - 13.7.2007, 22:26 |
|||
|
||||
Дата 13.7.2007, 22:25 (
Загрузка ...
| JackYF |
|
|||
 полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: 2 Всего: 162 |
Одна из олимпиадных задач. Нахождение максимальных подпрямоугольников.
Решается методом динамического программирования. Это точно. Дальше мои собственные рассуждения... не буду судить эффективность, но идея такая: Есть функция, которая принимает как параметр прямоугольник. Она рекурсивна, будет вызывать сама себя. Так вот. Функция при получении прямоугольника первым делом ищет неизмененный пиксель внутри. Каким методом - точно не знаю. Вообще говоря - лучше спиральным методом, начиная из середины. Если такового нету - весь прямоугольник на выход. Если нашелся, то формируем четыре внутренних подпрямоугольника максимальных размеров, которые расположены впритык к данной ячейке, соответственно сверху, снизу, слева и справа. И рекурсивно вызывается эта же функция для этих подпрямоугольников. |
|||
|
||||
| Ak47black |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 2205 Регистрация: 2.12.2005 Репутация: нет Всего: 0 |
Не тут не с олимпиады.
 Тут немного другая задача. Надо пройтись по всем байтам и составить массив прямоугольников. Я пробовал уже в два этапа 1. Вычисление прямоугольников. 2. Объединение похожих Но теряю некоторые и очень трудно засечь утечку.Добавлено через 7 минут и 14 секунд А нигде про это не писалось, я имею ввиду может гдето это уже описовась. Как-бы мне тут лучше подойти. Это сообщение отредактировал(а) Ak47black - 13.7.2007, 23:32 |
|||
|
||||
| JackYF |
|
||||
|
полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: 2 Всего: 162 |
ну то я к примеру.
чем отличается? надо составить массив прямоугольников. Верно? Мой алгоритм его и составляет. |
||||
|
|||||
| Ak47black |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 2205 Регистрация: 2.12.2005 Репутация: нет Всего: 0 |
JackYF, ну что я неособо могу представить как эти выполнить.
А ты откуданибудь взял может? |
|||
|
||||
| JackYF |
|
|||
|
полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: 2 Всего: 162 |
что взял? |
|||
|
||||
| Ak47black |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 2205 Регистрация: 2.12.2005 Репутация: нет Всего: 0 |
JackYF,
Я тут понял что я мой алгоритм нормально работает, проблема было не изза него. Сорри что поднял эту тему. Это сообщение отредактировал(а) Ak47black - 14.7.2007, 20:21 |
|||
|
||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.0466 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |