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 :)
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.11.2024 04:38:09 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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.
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.
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!
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.You need not use bitmasks.You can just use map in C++.Though it is a little slow,but is easy to write.