Намери най-краткия път през лабиринт. Звучи просто, докато в него не се появят заключени врати, ключове, кал и милион клетки. Задачата е в олимпиаден формат: вход, изход, тестове с верни отговори и ограничение във времето.
На първия ред са R C, броят на редовете и на колоните (до 1001 × 1001). Следват R реда по C символа. Лабиринтът винаги е ограден със стени.
| Символ | Значение |
|---|---|
| # | стена |
| . | свободна клетка |
| S | старт (точно един) |
| E | изход (точно един) |
| a b c d | ключ: взима се автоматично при стъпване и остава завинаги |
| A B C D | врата: минава се само ако вече имаш съответния ключ. Вратата не се изразходва. |
| ~ | кал: стъпката в тази клетка струва 3 вместо 1 |
Движението е в 4 посоки. Всяка стъпка струва 1, а стъпка в кал струва 3. Изходът е едно число: минималната цена от S до E, или -1, ако изходът е недостижим.
10 теста: файлове 01.in … 10.in с верните отговори в 01.out … 10.out.
| Тест | Размер | Съдържа | Етап |
|---|---|---|---|
| 01–04 | до 101 × 101 | само стени (04 е без изход) | 1 |
| 05 | 1001 × 1001 | само стени, проверка на бързодействието | 1 |
| 06–08 | до 301 × 301 | ключове и врати (до 4 вида) | 3 |
| 09 | 201 × 201 | кал | 4 |
| 10 | 401 × 401 | всичко заедно | 4 |
Само стени, свободни клетки, старт и изход.
5 7 ####### #S..#.# #.#.#.# #.#...E #######
7
4 5 ##### #S#E# #.#.# #####
-1
Готово, когато: тестове 01–05 минават. Тест 05 има милион клетки. Ако решението търси с рекурсия в дълбочина, вероятно ще препълни стека. Защо?
С флаг --put програмата отпечатва и самия лабиринт, в който клетките от намерения път са отбелязани със *.
Най-кратките пътища може да са няколко, затова тук няма един верен изход. Самопроверка: броят на звездичките трябва да е с 1 по-малък от отговора (S и E не се отбелязват).
Готово, когато: можеш да обясниш как възстановяваш пътя, без да пазиш целия път за всяка клетка.
Сега една и съща клетка може да се посети повече от веднъж и това да е правилно: веднъж без ключ, а по-късно с ключ.
5 9 ######### #S..A..E# #.#####.# #..a....# #########
10
5 9 ######### #S..A..E# #.####### #..a....# #########
14
7 13 ############# #S......#...# #.#####.#.#.# #.B.a.#A#.#.# #.###.#.###.# #..b#......E# #############
22
Какво точно е „състояние“ в тази задача? Позицията вече не стига. Как да запишеш кои ключове имаш в едно цяло число? Колко различни състояния има най-много при 4 вида ключове?
Готово, когато: тестове 06–08 минават.
Стъпките вече не струват еднакво. Алгоритъмът от етап 1 спира да дава верен отговор. Първо намери пример, в който греши, и едва след това го поправи.
5 7 ####### #S~~~E# #.###.# #.....# #######
8
Готово, когато: всички 10 теста минават, включително тест 10, където всичко е заедно.
Напиши генератор на лабиринти в същия формат. Изисквания:
Покажи търсенето в движение с произволна технология: как фронтът се разширява от S, как се заобикаля калта, как търсенето се връща за ключ. Сравни визуално етап 1 и етап 4 върху един и същи лабиринт.