| Fişierul intrare/ieşire: | dungeon2.in, dungeon2.out | Sursă | EJOI 2021, ziua 2 |
| Autor | Lucian Bicsi | Adăugată de |  Voicu Mihai-Valeriu •cadmium_ |
| Timp execuţie pe test | 1.625 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dungeon2
Dungeon Crawl: Paper Soup tocmai a devenit cel mai popular joc, iar tu eşti pe cale să îl încerci. Jocul se desfăşoară pe un teren dreptunghiular cu N linii şi M coloane, unde fiecare celulă este de unul dintre cele cinci tipuri descrise mai jos:
• celulă liberă '.';
• perete '#';
• celulă cu monedă 'o';
• celulă cu mină explozivă 'X';
• celulă de start 'S';
Se garantează că pe prima, respectiv ultima linie şi coloană se află pereţi (de precizat că este imposibilă deplasarea prin pereţi). Terenul poate conţine una sau mai multe celule de start. În momentul în care jocul începe, jucătorul va fi poziţionat iniţial într-una dintre celulele de start, marcate cu 'S'. Deoarece jocul se desfăşoară într-un sistem de peşteri cu vizibilitate redusă (vezi numele jocului), jucătorul nu poate vedea toată harta, ci doar o zona de vizibilitate restrânsă, reprezentată de un pătrat de 3 × 3 centrat în poziţia sa curentă. Mai mult, în această zonă de vizibilitate minele şi celulele de start apar drept celule libere (sunt invizibile pentru jucător).
La fiecare pas, jucătorul poate să se mişte pe direcţiile nord, sud, est sau vest. Dacă acesta ajunge pe o poziţie cu o monedă, colectează moneda, iar aceasta dispare de pe hartă. Dacă acesta ajunge pe o
poziţie cu mină, sistemul de peşteri se prăbuşeste, jucătorul pierde toate monezile colectate până în acel moment, iar jocul se termină.
Din fericire, urmărind diverse ghiduri pe internet ai aflat harta exactă a terenului, însă nu ştii în care dintre punctele de start vei fi repartizat – este garantat însă că vei porni dintr-o celulă de start. Considerând căvei adopta cea mai bună strategie, care este numărul maxim de monezi pe care îl poţi obţine garantat, indiferent de unde vei fi poziţionat la început?
Date de intrare
Pe prima linia a fişierul de intrare dungeon2.in se vor găsi valorile N şi M: dimensiunile terenului pe care se va desfăşura jocul, conform ghidurilor de pe internet. Următoarele N linii conţin fiecare câte un şir de caractere de lungime M, reprezentând harta, conform codificării descrise în enunţ.
Date de ieşire
În fişierul de ieşire dungeon2.out se va afişa un singur număr natural, numărul maxim de monezi care se poate obţine garantat pe acel teren.
Restricţii
- Fie S numărul de celule de start ce se află pe hartă.
- 1 ≤ S ≤ 60
- 1 ≤ N,M ≤ 400
- În plus:
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 3 | S = 1. Nu există mine. Cu excepţia primei şi ultimei linii şi coloane, nu există pereţi |
| 2 | 7 | N = 3 |
| 3 | 12 | S = 1 |
| 4 | 23 | S = 2 |
| 5 | 41 | 1 ≤ N,M ≤ 250, 1 ≤ S ≤ 12 |
| 6 | 14 | Nicio restricţie suplimentară |
Exemplu
| dungeon2.in | dungeon2.out |
|---|---|
| 3 7 ####### #Soooo# ####### | 4 |
| 3 8 ######## #SoXooS# ######## | 1 |
| 7 18 ################## #................# #.o...SX.......o.# #.o...X..X.....o.# #.o.....XS.....o.# #................# ################## | 0 |
| 7 18 ################## #....#...........# #.o...SX.......o.# #.o...X..X.....o.# #.o.....XS.....o.# #.........#......# ################## | 6 |
| 7 18 ################## #......X..S....oo# ################## #..o..S.X......o.# ##########X####### #o.....S...X.....# ################## | 1 |
Explicaţie
Exemplul 1. Există o singură poziţie de start, deci ştim exact de unde va porni jucătorul. În acest caz, jucătorul poate colecta toate monezile.
Exemplul 2. Sunt două poziţii de start, iar jucătorul poate deduce unde este poziţionat pe baza zonei de vizibilitate (*$@$* este poziţia jucătorului):
### ###
#@o o@#
### ###
Numărul maxim de monezi pe care le poate colecta jucătorul dacă porneşte din partea stângă este 1, respectiv 2 dacă porneşte din partea dreaptă. Deci, pe cel mai rău caz, putem colecta o monedă.
Exemplul 3. În orice direcţie s-ar mişca iniţial jucătorul, pe caz nefavorabil se va afla o mină în direcţia respectivă. Zona de vizibilitate iniţială este:
...
.@.
...
Exemplul 4. Jucătorul îşi poate da seama în care celulă a fost plasat iniţial, analizând zona de vizibilitate. Mai exact, acesta se uită dacă iniţial vede un perete în stânga-sus sau dreapta-jos; astfel, ştie exact cum să se poziţioneze pentru a evita minele. Zonele de vizibilitate iniţiale aferente celor două poziţii sunt:
#.. ...
.@. .@.
... ..#
Exemplul 5. Jucătorul se mută 2 paşi la stânga. Dacă vede o monedă la stânga, deduce că este în
zona din mijloc, o culege şi termină jocul. Dacă nu, ştie că nu este în zona din mijloc, aşa că se mută la dreapta 4 paşi.
Observând mai apoi dacă există spaţiu liber în dreapta-sus (minele sunt văzute drept spaţii libere),
poate deduce dacă se află în zona de sus sau zona de jos. În ambele cazuri, este liber să colecteze
moneda/monezile corespunzătoare. În cel mai nefavorabil caz, însă, va putea colecta o singură monedă.
Se poate observa că jucătorul nu se putea muta iniţial spre dreapta, deoarece ar fi riscat să atingă mina din centru pe caz nefavorabil.
