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

Shortest path using BFS question ?
Автор Live_Forever, 10 лет назад, По-английски

I am solving a question where I want to find the shortest path from a source to destination in a 2D unweighted graph picking up all the coins given. So, each vertex can be visited more than once. How do I solve it using BFS (or is there any better way to solve it) ? I'm unable to get my head around how to track back on the visited cells. Please help me . Thanks !

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you please provide a link to the problem, or explain it more?

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ok, there is a 2d maze with source (S) and destination (D) given. The maze also contains walls(W) through which we can't pass and coins (C). We've to find the shortest path from S to D ,picking up all the coins in the process. We can move only left,right,up and down.

    → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

I'll assume that the number of coins is small.

One way to solve it is to build a new complete graph with 2+C nodes: S, D, and a node for each coin, weight of an edge is the length of the shortest path between the two nodes, then find the shortest path using DP with bitmask, similar to TSP DP solution.

You can also solve it using BFS only, but your state should be [mask][r][c], so you will visit each cell at most 2^C times.

About bitmasks:

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation

http://mirror.codeforces.com/blog/entry/337

→ Ответить