Fișierul intrare/ieșire roboti.in, roboti.out Sursă ONI 2006 clasa necunoscuta
Autor Roxana Tîmplaru Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Roboti (clasa a 6-a)

Se consideră un caroiaj de forma unui pătrat cu n x n celule. Avem la dispoziție cel mult n x n roboței ce pot fi plasați în oricare din celulele caroiajului, cel mult un roboțel în fiecare celulă. Vom identifica roboțeii plasați în caroiaj prin litere mari care să indice în clar sensurile inițiale de deplasare, după cum urmează: un roboțel de tipul ′U′ (up) se va deplasa de jos în sus (din celula în care se află, în celula situată pe linia de deasupra și aceeași coloană) , un roboțel de tipul ′D′ (down) se va deplasa de sus în jos (din celula în care se află, în celula situată pe linia următoare și aceeași coloană), un roboțel de tipul ′L′ (left) se va deplasa de la dreapta la stânga (din celula în care se află, în celula situată pe aceeași linie și coloana din stânga), iar un roboțel de tipul ′R′ (right) se va deplasa de la stânga la dreapta (din celula în care se află, în celula situată pe aceeași linie și coloana din dreapta).

Deplasarea are loc pentru un număr cunoscut de pași k. Configurația inițială se consideră pasul 0. La fiecare pas i, fiecare robot se va deplasa într-o celulă vecină celei ocupate la pasul anterior i-1, în conformitate cu sensul lui de deplasare. De exemplu, un roboțel de tip U va avansa în celula plasată deasupra lui, așa cum un roboțel de tip L va avansa în celula plasată imediat în stânga celei curente. Este posibil ca traseele roboțeilor să se intersecteze sau să se suprapună. Dacă la un anumit pas, doi sau mai mulți roboței avansează în aceeași celulă, atunci are loc o mică implozie și, practic, acești roboței se dezintegrează și dispar de pe caroiaj.

În figura 1 este exemplificată o astfel de situație: roboțeii de tip D și R, prezenți în caroiaj la pasul i-1, dispar la pasul următor i, pentru că avansează amândoi în celula din mijlocul caroiajului, în timp ce roboțelul de tip U nu are astfel de probleme și își continuă deplasarea.

Să comentăm acum figura 2. Situația roboțeilor de tip D și U de la pasul i-1 poate părea conflictuală, însă ei urmează să avanseze în celule diferite la pasul următor i, motiv pentru care nu are loc dezintegrarea lor; practic fac schimb de locuri și își continuă deplasările.

În cadrul aceleiași figuri 2, pașii i și i+1 implică o analiză specială care impune noi reguli privind deplasarea roboțeilor. Este vorba de roboțeii de tip L și D care au atins marginile caroiajului și nu mai pot executa deplasări la stânga, respectiv în jos, conform tipurilor lor. În astfel de cazuri, sensurile de deplasare pur și simplu se inversează și odată cu asta se schimbă și tipurile roboțeilor. Așa cum se observă și în figură, roboțelul de tip L, la pasul i nu mai poate efectua deplasări la stânga, motiv pentru care se transformă în roboțel de tip R și se deplasează cu o celulă mai la dreapta la pasul i+1, conform regulilor de deplasare corespunzătoare noului său tip. La fel se petrec lucrurile și cu roboțelul de tip D de la pasul i care se transformă în roboțel de tip U la pasul i+1 și urcă o poziție în caroiaj. Evident că această regulă se aplică și roboțeilor de celelalte două tipuri R și U care, în situația în care ating marginile caroiajului, devin roboți de tip L și respectiv D, inversându-și practic sensurile de deplasare. Așa ar trebui să se întâmple lucrurile și în cazul roboțelului de tip U situat în colțul din dreapta sus al caroiajului la pasul i+1. El ar trebui să se transforme în roboțel de tip D și să ocupe o poziție mai jos în caroiaj la pasul i+2. Numai că această poziție este “revendicată” și de roboțelul de tip R. Conform celor discutate anterior, dacă doi sau mai mulți roboței avansează în aceeași celulă, ei se dezintegrează și dispar din caroiaj, așa cum este ilustrat și în figură. Roboțelul de tip D de la pasul i-1 este singurul care “a supraviețuit” până la pasul i+2, chiar dacă s-a transformat pe parcurs într-unul de tip U; rămânând singur în caroiaj, mișcarea sa continuă la nesfârșit, având în vedere schimbările corespunzătoare de sens și de tip, ori de câte ori este cazul.

Cerință

Dându-se configurația ințială a caroiajului și un număr specificat de pași k, afișați numărul de roboți care vor mai rămâne în caroiaj și configurația obținută după k pași.

Date de intrare

Fișierul de intrare roboti.in contine pe prima linie numărul natural n (dimensiunea caroiajului). Pe cea de a doua linie se află numărul natural k (numărul de pași). Pe următoarele n linii se află câte n caractere din mulțimnea {′U′, ′D′, ′L′, ′R′,′.′} (obligatoriu litere mari). Dacă celula nu conține nici un roboțel, atunci i se asociază caracterul ′.′ (caracterul punct), în caz contrar, celula conține un roboțel și atunci i se asociază unul din caracterele ′U′, ′D′, ′L′ sau ′R′, în conformitate cu tipul inițial al roboțelului plasat în celulă.

Date de ieșire

Fișierul de ieșire roboti.out va conține pe prima linie numărul de roboței care au rămas în caroiaj după k pași. Pe următoarele n linii se vor afișa cele n x n valori care reprezintă configurația caroiajului după k pași, sub forma a n linii, fiecare linie conținând n caractere care pot fi: U, D, L, R sau . (caracterul punct).

Restricții

  • 2 ≤ n ≤ 20
  • 1 ≤ k ≤ 100
  • Fișierele de intrare/ieșire nu conțin spații.

Exemplu

roboti.in roboti.out
3
4
...
.RD
..U
1
...
..D
...

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii