Fişierul intrare/ieşire:sokoban.in, sokoban.outSursăFinala ONIS 2016
AutorMihai CalanceaAdăugată deandreiiiiPopa Andrei andreiiii
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.insokoban.out
1
10 12
.##########.
.#........#.
.#..X..S..##
.#.#..####.#
.###..E....#
##.#....#.##
#..##.###.##
#.........##
#..#..##...#
############
YES
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?