| 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 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.
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
| sokoban.in | sokoban.out |
|---|---|
| 1 10 12 .##########. .#........#. .#..X..S..## .#.#..####.# .###..E....# ##.#....#.## #..##.###.## #.........## #..#..##...# ############ | YES |
