ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1367. Конфиденциально!

Test 2 Incorrect!
Послано svr 4 дек 2006 00:48
My program solves all testes on forum
but has WA2.
After some experiments I established that test 2 has
form : xx+xx
       x#|#x
where symbols x are not important
It is obvious that secrets # mutually unreacheable
But experiments say that test has it's answer 11
                                              11
Re: Test 2 Incorrect!
Послано svr 17 дек 2007 15:55
Reading ЧАВО helped. Was mistake of input.
But problem has appeared rather difficult.
Approach with Dfs from each # leads to TLE.
It is necessary take to acount topology.
Field consists of some lakes closed by + and #.
We should start Dfs from inside of these lakes and
#-s found this time on boundary are mutually achievable.
AC!.
P.S. It helpfull to make relation of approachibility having
transitiveness property to be equivalence. It can be made
by dividing one big cell in 4 smaller ones and moving
along them.

Edited by author 20.12.2007 07:56