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

Poveste şi cerinţă...

h2. Date de intrare

h2. Restricţii

* Suma de $max(N, M)$ pentru fiecare test este mai mica sau egala cu $2000$.

* Suma de $max(N, M)$ pentru fiecare test este mai mica sau egala cu $2000$

h2. Exemplu