phantom11's blog

Maze traversal
By phantom11, 13 years ago, In English
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??
  • Vote: I like it
  • -21
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
dp[maskOfVisitedBluePositions][currentBluePosition]
Similar problems:
http://codeforces.net/problemset/problem/8/C
http://acm.sgu.ru/problem.php?contest=0&problem=536
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Ok.But the problem 8C does not talk about the non-visiting vertex.How to handle those??
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      When you calculate shortest distances from one blue position to another, you should not go through red positions
      → Reply