Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя phantom11

Maze traversal
Автор phantom11, 13 лет назад, По-английски
There is a maze of size NxN.You need to find the shortest path from 'S' to 'E' making sure you reach all blue positions marked 'B' and do not reach any red position marked 'R'.If there is no path then print -1.
How to solve this problem??
  • Проголосовать: нравится
  • -21
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
dp[maskOfVisitedBluePositions][currentBluePosition]
Similar problems:
http://mirror.codeforces.com/problemset/problem/8/C
http://acm.sgu.ru/problem.php?contest=0&problem=536
→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ok.But the problem 8C does not talk about the non-visiting vertex.How to handle those??
    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      When you calculate shortest distances from one blue position to another, you should not go through red positions
      → Ответить