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

_Notă: Se recomanda folosirea compilatorului GNU C++ pe 32 de biti._
 

Tocmai ţi-ai descărcat ultima versiune a binecunoscutului joc Plante şi Zombi. Jocul se joacă pe un teren finit 2D în care vor apărea mai mulţi zombi. Fiecare zombie are o poziţie de început $(S[~x~], S[~y~])$ în care apare, o viteză de $v$ unităţi/secundă şi un şir de exact 15 mutări pe care le va face. O mutare este codificată printr-un caracter din mulţimea ${U, R, D, L}$ ("up", "right", "down", "left").
Zombii vor executa mutările secvenţial, pornind de la prima mutare. Fiecare zombie se va mişca în direcţia indicată de mutarea curentă timp de exact o secundă, după care va trece la mutarea următoare. De exemplu, dacă un zombie are viteză $3$, începe de pe poziţia $(2, 4)$ şi prima mutare este $U$, acesta va executa mutările $(2, 4) -> (2, 5) -> (2, 6) -> (2, 7)$ într-o secundă, după care va trece la următoarea mutare. Pentru mai multe informaţii, vezi explicaţiile.

Pe prima linie se afla *N* reprezentând numărul de zombii.
Pe urmatoarele *N* linii se află câte 3 numere *Sx Sy v* si un sir de 15 caractere *S* reprezentând parametrii fiecărui zombie aţa cum sunt descrişi în enunţ, in ordine.

*Se garantează că şirul de mutări ale fiecărui zombie are lungime exact 15.*
 

h2. Date de ieşire
Pe prima linie se va afişa *M* reprezentând numărul minim de plante cerut.
Pe următoarele *M* linii se vor afişa parametrii fiecărei plante: 2 numere *lx ly* reprezentând poziţia plantei şi un caracter reprezentând direcţia laserului plantei respective.

h2. Detalii de implementare
 
Veţi implementa funcţia cu următorul antet:
 
== code(cpp) |
 
std::vector<Plant> minimum_plants(std::vector<Zombie> zombies)
 
==
 
Structurile de date folosite în cadrul interacţiunii sunt descrise în fişierul *zombies.h* şi au următoarea descriere:
 
== code(cpp) |
 
struct Zombie {int sx, sy, v; string moves; };
struct Plant {int lx, ly; char dir; };
 
==
 
Funcţia $minimum_plants$ va fi apelată o singură dată, parametrii având specificaţiile din enunţ. *Se garantează că şirul de mutări ale fiecărui zombie are lungime exact 15.*
 

Pentru ca soluţia returnată să fie validă, trebuie ca numărul de plante-laser returnate să fie minimul posibil şi ca plantele să neutralizeze toţi zombii. De asemenea, plantele trebuie plasate în poziţii distincte, iar coordonatele $l[~x~]$ şi $l[~y~]$ trebuie să fie numere întregi între $-10^9^$ şi $10^9^$ inclusiv.
h2. Punctare