== include(page="template/taskheader" task_id="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:

_$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 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).

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ă.

* $1 ≤ S ≤ 60$
* $1 ≤ N,M ≤ 400$
* În plus:

table(restrictii). |_. # |_. 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ă |

| $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ă |

h2. Exemplu
table(example). |_. dungeon2.in |_. dungeon2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

h3. 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.
 
 

== include(page="template/taskfooter" task_id="dungeon2") ==