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

Care este numărul minim de plante-laser care trebuie plasate pentru ca fiecare zombie să fie neutralizat la un moment dat pe parcursul jocului?

h2. Date de intrare

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:

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.

== code(cpp) |

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

struct Zombie {int sx, sy, v; string moves; };
struct Plant {int lx, ly; char dir; };

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.

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.