== 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 *$'#'$*;

* Î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ă |

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") ==