1 Тема от xenobit Отредактировано xenobit (2010-11-17 18:08:50)

  • xenobit
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-14
  • Сообщений: 3

Тема: acm.sgu.ru #527-Explode 'Em All

Как этот mad bomberman решается?

2 Ответ от xenobit

  • xenobit
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-14
  • Сообщений: 3

Re: acm.sgu.ru #527-Explode 'Em All

Пробовал поиском в ширину, бэктрекингом по стокам, маскам. Конечно же ТЛ. Есть другое решение или бэктрекинг оптимизировать нужно?

3 Ответ от Oleg

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: acm.sgu.ru #527-Explode 'Em All

Думай в сторону графов и минимального контролирующего множества.

4 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: acm.sgu.ru #527-Explode 'Em All

xenobit пишет:

Пробовал поиском в ширину, бэктрекингом по стокам, маскам. Конечно же ТЛ. Есть другое решение или бэктрекинг оптимизировать нужно?

Ну кстати, перебор по маскам за O(2^N) отлично проходит.

5 Ответ от Oleg

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: acm.sgu.ru #527-Explode 'Em All

Идея с минимального контролирующего множества провалилась. sad Пошло бы если бы бомбой уничтожали только ряд или только колонку.
Сдал перебором всех возможных колонок.  Интересно как ее за 22ms решили.