red_coder's blog

BFS with Bitmasks..
By red_coder, 12 years ago, In English

Can anyone suggest me how to Solve this Problem using BFS along with Bitmasks.... Never solved problems of this kind before so need some help :)

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

»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

See the editorial here.

========================== D. There is just BFS. State is head place and mask that store place of tail: using 2 bits you can code position of every segment in relation to previous segment. Mask will contain no more than 16 bits, and number of all states will be no more than 48 × 15 × 15 (also you can try understand that number of states no more than 38 × 15 × 15).

Then you should just carefully implement it.

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

    Actually till now i have only used little bit of BFS and that too on simple graphs. I read the editorial but it said BFS along with states using bitmasks. This went above my head. Can u give me some link from where i can read how to use bfs involving states and bitmasks.

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

      You just should learn how to use bit masks in different situations. If you can use bit masks well, it wouldn't be problem for you to involve it in any problems and the solution of this problem would be obvious for you ;) Good luck!

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      You don't know bitmasks? You could learn it on Wiki: http://en.wikipedia.org/wiki/Mask_(computing) . Then you could use in C++ to record states easily.

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

You need not use bitmasks.You can just use map in C++.Though it is a little slow,but is easy to write.

→ Reply