| 1 Мещеряков Савелий Иванович, 26 января 2026 г. 15:27:19 |
| каких 51 процент это максимум 30 за то что граф. бфс влоб просто
|
|
|
| 2 Неизвестный, 27 ноября 2025 г. 17:48:19 |
| Можно конвертировать двумерноы массив в одномерный.Этим способом решать легче по моему
|
|
|
| 3 Неизвестный, 27 ноября 2025 г. 17:47:43 |
| Когда будете решать с BFS,сначала добавите позиции всех 1 в очередь ну потом начните BFS
|
|
|
| 4 Сташевский Александр Витальевич, 31 октября 2025 г. 8:55:26 |
| Тут просто надо BFS запустить от всех единиц
|
|
|
| 5 Караулов Иван Дмитриевич, 21 декабря 2023 г. 22:29:31 |
| никакой бфс, дфс не нужен, не усложняйте себе жизнь, за н^4 спокойно заходит
|
|
|
| 6 Владимир Владимирович Владимир, 01 августа 2023 г. 15:42:36 |
| Всем привет, задача непростая, основная идея - bfs с запуском из всех вершин со значением 1. Для этого их нужно добавить сразу в очередь, а потом из каждой шагать с ходом 1. В шахматных терминах: в каждой клетке 1 стоит король, у королей задача посетить побольше клеток. Необходимо понять, через сколько шагов клетку займут.
|
|
|
| 7 Сомони Фазлиддин, 26 февраля 2022 г. 19:01:26 |
| Простой перебор! Халява!
|
|
|
| 8 Веретельников Никита Владиславович, 13 мая 2021 г. 21:00:54 |
| Сделал оптимизированный bfs от каждой единицы, идем пока все еще можем улучшить длину пути из текущих клеток.
|
|
|
| 9 Севидов Артём Алексеевич, 15 апреля 2021 г. 17:57:36 |
| Не знаю,зачем вам тут количество единиц,просто запускаем bfs одновременно от всех единиц(это обосновывается введением фиктивной вершины x,расстояние от которой до всех единиц 0) Каждую клетку мы посетим один раз ,а просмотрим не более 4(с четырех сторон),поэтому сложность O(N*M)
|
|
|
| 10 Махмадиеров Фахриддин, 25 декабря 2020 г. 11:02:37 |
| BruteForce, O(N*M*k1), k1-number of 1
|
|
|
| 11 Трохачев Андрей Вадимович, 31 января 2020 г. 18:40:14 |
Решил за O(nlogn) через Multi-Source bfs. Можно ли решать задачу за линию?
Любой bfs не даёт log в O большом.
|
|
|
| 12 Неизвестный, 12 сентября 2019 г. 18:07:54 |
| Решил за O(k*f) k-кол-во единиц,f-кол-во нулей
|
|
|
| 13 Виденеев Илья Владимирович, 16 августа 2019 г. 15:17:18 |
| тут даже графы не нужны, тупо перебором решается, как задача "Вирусы"
|
|
|
| 14 Смирнов Илья Сергеевич, 07 августа 2019 г. 11:37:35 |
| Подскажите,пожалуйста,как выйти на сложность O(N*M) ? Разве не будет оптимальным запускать BFS от каждой единицы и обновлять значения в клетках таблицы? Тут получается O(k*N*M),k - кол-во единиц
|
|
|
| 15 Якина Ангелина Ивановна, 15 июня 2019 г. 15:29:54 |
Возможно, я как-то неправильно поняла условие задачи, но я писала Дейкстру с кучей. Как итог - Accepted (хотя мне кажется, эту задачу можно решить, например, шириной).
Если все длины рёбер равны (как в случае этой задачи), то вместо алгоритма Дейкстры конечно же можно использовать поиск в ширину.
|
|
|
| 16 Сидоревич Антон Валерьевич, 28 августа 2017 г. 15:03:11 |
| Можно эту задачу сделать более сложной с решением за O(N*M)
|
|
|
| 17 Зубашев Степан, 27 июля 2016 г. 19:01:01 |
| Решил и с BFS, заодно его распробовав. На такой малой выборке разница заметна только по сложности кода ;)
|
|
|
| 18 Зубашев Степан, 26 июля 2016 г. 21:32:25 |
Решил грубо. Кажется: O(N^2 * M^2). При данных ограничениях с огромным резервом проходит перебором. Без двумерных массивов, векторов и пр. Просто массив координат точек, массив координат единиц. Для каждого 0 сравнение с каждой точкой, минимальный результат в вывод.
Судя по ответам админа не комильфо. Пожалуй стоит решить ещё и через БФС.
|
|
|
| 19 Глейх Андрей Артурович, 11 октября 2012 г. 11:02:33 |
Ну что я могу сказать: при сравнении одного и того же алгоритма на Java и на C++ STL стало мне очевидно что STL рулит. Там где у Java TLE, С++ запросто проходит. А асимптотика алгоритма ниже указана Нурланом
У Нурлана странная асимптотика
|
|
|
| 20 Тулегенов Нурлан, 14 июня 2012 г. 10:50:05 |
У меня получилось O(k0 * k1) где k0 - количество нулей k1 - количество единичек
Иными словами, в худшем случае, когда нулей и единиц поровну, то получается сложность алгоритма O(N^2*M^2), т.е. плохая у Вас асимптотика, но при данных ограничениях может теоретически пройти. Но я полагаю, что скорее всего Вы неверно асимптотику посчитали. При использовании BFS получается сложность O(N*M), и очевидно лучшей асимптотики быть не может.
|
|
|
