Dospra Cristian (cristi_dospra) Renumitul nostru brutar a avut azi noapte un vis tare ciudat: acesta trăia într-un univers paralel în care nu omul îl mănâncă pe blat ci blatul îl mănâncă pe om… (eh, poate nu chiar atât de paralel). Astfel, brutarul nostru a fost atacat de blatul pe care tocmai îl pregătise (pentru prăjituri, evident) și a încercat să scape. Acesta a ieșit din brutărie și a ajuns în fața unui câmp de formă dreptunghiulară, cu dimensiunile cunoscute, ce poate fi împărțit în celule elementare cu latura de o unitate (exact ca o matrice!). Acesta poate intra pe câmp prin orice celulă a primei linii și trebuie să ajungă în orice celulă a ultimei linii (blatul se va întări până va ajunge acolo). Unele celule îi sunt inaccesibile din cauza diverselor obstacole (pietre, pomi, gropi,etc.)
Brutarul nostru se poate deplasa în 6 moduri:
- Din căsuța curentă în cele adiacente (
Nord,Vest,Sud,Est) - Două mișcări speciale ce pot varia.
Mutările speciale vor fi citite din fișier și o mutare se va codifica astfel: xA yB, unde x și y sunt numere naturale nenule iar A și B sunt două caractere ce codifică direcția (A poate fi 'N' sau 'S' de la Nord respectiv Sud iar B poate fi ‘E’ sau ‘V’ de la Est respectiv Vest)
Ex. 5N 2V codifică mutarea 5 poziții spre Nord și 2 poziții spre Vest. (din poziția (x,y) ajunge în poziția (x-5, y-2))
O mutare specială se poate face dacă celula destinație nu este ocupată de un obstacol și dacă nu implică ieșirea brutarului din matrice.
Cerința
Brutarul vă roagă să îi specificați un traseu cu număr minim de celule parcurse, ce pornește de pe prima linie și se termină pe ultima linie, pentru a nu fi blătuit (mâncat de blat).
Date de intrare
Pe prima linie a fișierului brutar.in se vor afla două numere naturale separate prin spațiu: N și M reprezentând numărul de linii și numărul de coloane ale câmpului. Urmează N linii a câte M caractere ‘X’ și ‘O’ unde ‘X' reprezintă obstacol iar ‘O’ reprezintă zonă liberă.
Ultimele două linii reprezintă codificarea celor două mutări speciale, câte o mutare pe o linie.
Date de ieșire
Fișierul brutar.out va conține, pe prima linie, numărul T de celule al unui traseu de lungime minimă. Următoarele T linii vor conține descrierea traseului, câte o celulă pe o linie, prin coordonatele ei, în ordinea în care au fost parcurse.
Restricții și precizări
1 ≤ N, M ≤ 1.0001 ≤ x ≤ N1 ≤ y ≤ M- Se garantează că mereu va există cel puțin un drum care pornește de pe prima linie și ajunge pe ultima linie a matricei.
- Dacă există mai multe soluții cu număr minim de pași, se poate afișa oricare dintre acestea.
Exemplu:
brutar.in
14 10 XXXXXXOXXX OXOOOXOOOO OOXXOOXOXO OXOOOOXXXX OOOOXXOXOX OXOXOXXOOO XOXOOOOXOO OXXXOXOOOX XOOXOXOXOO OXOXOXOXOO OOOOXXOOXO XOOOXOXOOX OXOOOOOOOO XOXXXOXXXX 2S 1V 2S 1E
brutar.out
9 1 7 3 6 5 7 7 6 9 5 10 5 12 4 12 3 14 2
Explicație
Drumul este colorat în galben:
