Live_Forever's blog

Shortest path using BFS question ?
By Live_Forever, 10 years ago, In English

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 !

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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://codeforces.net/blog/entry/337

→ Reply