I. Sokoban

Sokoban

== include(page="template/taskheader" task_id="sokoban") ==

Este posibil ca unii dintre voi să ştie jocul Sokoban. Acesta are loc pe o matrice cu $N$ linii şi $M$ coloane. Unele celule sunt libere (notate cu '.'), iar altele sunt blocate (notate cu '#'). Exact o celulă (notată cu 'S') este ocupată de jucător. Exact o celulă (notată cu 'X') este ocupată de o cutie. Exact o celulă (notată cu 'E') este desemnată celula destinaţie. Scopul jucătorului este să împingă cutia până la celula destinaţie. Jucătorul poate împinge cutia într-o anumită direcţie dacă se află într-o celulă alăturată cutiei (pe cele 4 direcţii NSVE) iar poziţia sa relativ la cutie este opusă direcţiei în care acesta doreşte să împingă cutia. Spre exemplu, dacă el se află exact în stânga cutiei, o poate împinge la dreapta. Pentru ca mişcarea să se poată realiza, trebuie ca celula în care este impinsa cutia să fie liberă. De-asemenea, jucatorul poate sa acceseze doar celule libere. Cutia este solidă, iar jucătorul nu poate trece printr-o celulă dacă aceasta este ocupată de cutie. Jucatorul poate trece peste celulele de start sau destinatie.

Este posibil ca unii din voi să ştiţi jocul Sokoban. Acesta are loc pe o matrice cu $N$ linii şi $M$ coloane. Celulele matricei pot fi egale cu:

Dându-se o instanţă a jocului, voi trebuie să decideţi dacă aceasta are soluţie, i.e dacă este posibil ca jucătorul să împingă cutia din poziţia ei de start până la celula destinaţie.

- '.'

h2. Date de intrare