|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
02.08.2019, 13:11 | #1 |
Пользователь
Регистрация: 11.05.2019
Сообщений: 21
|
Решение задачи из архива acmp (432)
Здравствуйте,
я решаю задачу 432 из архива acmp (http://acmp.ru/?main=task&id_task=432) сначала я решил задачу с помощью булевой матрицы и обходом в глубину, однако тест по времени не был пройден. сейчас я решаю эту задачу с помощью системы непересекающихся множеств, однако имею некоторые проблемы с реализацией на C++ вкратце содержание кода: 1) считывает input, строит двухмерный массив 2) определяет стэк, куда складываются посещенные клетки при условии, что их значение равно единице. 3) в функции check происходит проверка тех клеток, которые принадлежат данной (по условию задачи - это окрестность фон Неймана первого порядка). Если клетка принадлежит - ее координаты - в стэк? а ее множество объединить с данной. Пока стэк не пуст, повторять check() 4) Согласно идеи, в конце имеет массив p, где имеет повторяющиеся числа на позициях клеток, значение которых единица. Количество различных чисел на таких позициях и есть ответ на вопрос задачи. Код:
Прошу проверить код на корректность. |
05.08.2019, 19:53 | #2 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
Она не так решается.
Формально - нужно найти количество компонент связности. Вот и ищите. Запускайте дфс/бвс и все. Никак dsu не надо |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Оптимизация (сокращение) кода решения задачи #2 c acmp.ru - нахождение суммы целых чисел от 1 до N | Serge_Bliznykov | Помощь студентам | 31 | 23.08.2014 22:35 |
Решение задачи #71 на acmp.ru | Poma][a | Паскаль, Turbo Pascal, PascalABC.NET | 9 | 28.08.2013 22:09 |
Оптимизация (сокращение) кода решения задачи #46 c acmp.ru - вывод числа E с заданной точностью | Poma][a | Паскаль, Turbo Pascal, PascalABC.NET | 47 | 05.07.2013 23:50 |
Олимпиадные Задачи (с acmp.ru) | Poma][a | Паскаль, Turbo Pascal, PascalABC.NET | 7 | 20.12.2012 07:44 |
Решение задачи | l1merain | Общие вопросы C/C++ | 0 | 21.10.2011 18:29 |