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

Автор red_coder, 12 лет назад, По-английски

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 :)

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

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

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.

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

    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.

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

      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!

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

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

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