Fişierul intrare/ieşire:	sokoban.in, sokoban.out	Sursă	Finala ONIS 2016
Autor	Mihai Calancea	Adăugată de	Popa Andrei •andreiiii
Timp execuţie pe test	0.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sokoban

Este posibil ca unii din voi să ştiţi 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 împingem cutia să fie liberă. Cutia este solidă, iar jucătorul nu poate trece printr-o celulă dacă aceasta este ocupată de cutie.

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.

Date de intrare

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

Date de ieşire

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

Restricţii

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

Exemplu

Cum se trimit solutii?