|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
07.04.2011, 16:49 | #1 |
Пользователь
Регистрация: 07.06.2009
Сообщений: 43
|
Какой алгоритм использовать?
Задача: Есть матрица MxN
в ней есть некоторое количество нулей и не нулей. наугад выбирается элемент матрицы и если он нулевой требуется определить максимально широкую область из нулей в которой он лежит и в ответ дать ее границу. Поясню на примере: 1100100 1120022 2200200 2211111 1110000 для элемента (3,3) ответом будет помеченные звездочками клетки: 1*00*00 1**00** 1*00*00 2****** 1110000 При обходе разрешено перемещаться по горизонтали, вертикали и диагонали, при этом в области могут быть "дырки", то есть двойная граница... ******* *00000* *0***0* *0*0*0* *0***0* *00000* ******* Количество таких "дырок" неизвестно наперед... На ум идет ужасно страшный перебор, экспоненциальной сложности вида: проверять на то, достижима ли эта клетка из текущей, потом проверить достижима ли соседняя и если не так то считать ее граничной и добавить ее номер в стек... и второе - хранить в списке сначала эту клетку, потом все достижимые нулевые клетки из нее за 1 шаг, потом расширить до 2 шага и когда список не будет меняться то это и есть граница... но все это наверное слишком страшные алгоритмы - может есть по-проще? |
07.04.2011, 19:03 | #2 |
Форумчанин
Регистрация: 25.12.2010
Сообщений: 247
|
Можно поиском в глубину
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Какой компонент использовать | Кинельски | Компоненты Delphi | 5 | 23.06.2010 11:10 |
КАКОЙ КОМПОНЕНТ НАДО ИСПОЛЬЗОВАТЬ? | Gareevbo | Общие вопросы Delphi | 2 | 08.06.2009 22:33 |
Какой компонент использовать? | XPAiN | БД в Delphi | 3 | 05.05.2008 08:45 |