Sokoban

I. Sokoban

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

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $sokoban.in$ ...

Fişierul de intrare $sokoban.in$ va conţine pe prima sa linie numărul de teste, $T$. Fiecare test respectă următoarea structură: prima linie conţine valorile $N$ şi $M$, reprezentând numărul de linii, respectiv numărul de coloane al matricei. Următoarele $N$ linii conţin câte $M$ caractere, care pot fi '.', '#', 'X', 'S', sau 'E'.

h2. Date de ieşire

În fişierul de ieşire $sokoban.out$ ...

În fişierul de ieşire $sokoban.out$ se vor afla $T$ linii, fiecare conţinând cuvântul $YES$ sau $NO$.

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