2588 - Iepuras1
Un iepuraş se găseşte într-o grădină plină de surprize. Harta grădinii poate fi reprezentată sub forma unei table dreptunghiulare cu m linii, numerotate de la 1 la m de sus în jos, şi n coloane, numerotate de la 1 la n de la stânga la dreapta. În fiecare celulă a acestei grădini se poate găsi cel mult una dintre următoarele surprize: săgeată, pom, zid, trapă, morcov, bombă.
O săgeată indică una din direcţiile nord, sud, est, vest. Odată ajuns într-o celulă conţinând o astfel de săgeată iepuraşul îşi va continua deplasarea în sensul indicat de săgeată, iar aceasta dispare.
Într-o celulă în care se găseşte un pom sau un zid iepuraşul nu poate să pătrundă, însă dacă se “loveşte” de un pom, el îşi păstrează direcţia, însă schimbă sensul (dacă se deplasa spre nord, îşi va schimba sensul spre sud, dacă se deplasa spre est, se va deplasa după aceea spre vest etc).
Dacă iepuraşul intră într-o celulă conţinând o trapă, toate zidurile aflate pe teren dispar şi vor apărea alte ziduri, în poziţii precizate. Dacă iepuraşul va trece din nou printr-o celulă conţinând o trapă, zidurile nou construite dispar şi vor reapărea zidurile iniţiale. Mai exact există două grupe de ziduri care comută la fiecare trecere printr-o celulă care conţine o trapă.
Dacă iepuraşul va trece de două ori prin vecinătatea unei celule conţinând o bombă (adică prin celulele învecinate la sud, nord, est sau vest cu celula conţinând bombă), bomba va exploda iar iepuraşul se transformă instantaneu în îngeraş. De asemenea, dacă iepuraşul întră într-o celulă conţinând o bombă se transformă instantaneu în îngeraș.
Iepuraşul va ronţăi toţi morcovii care îi ies în cale. Evident că dacă trece a doua oară prin aceeaşi celulă, la a doua trecere nu va mai găsi morcov.
Surprizele din grădină sunt codificate astfel: 1 pentru săgeată spre nord, 2 pentru săgeată spre vest, 3 pentru săgeată spre sud, 4 pentru săgeată spre est, 5 pentru pom, 6 pentru bombă, 7 pentru morcov, 8 pentru zid, 9 pentru trapă. Căsuţele libere de pe harta grădinii se codifică cu 0.
Iniţial, se cunosc poziţia şi sensul de deplasare ale iepuraşului. Expediţia acestuia se termină în următoarele situaţii:
- la explozia unei bombe, caz in care se transforma in ingeras;
- la parasirea gradinii (adica la iesirea in afara zonei dreptunghiulare date), caz in care se rataceste;
- in momentul in care reuseste sa rontaie toti morcovii, caz in care este fericit.
Cerința
Fiind data harta grădinii se cere să se determine starea finală a iepuraşului (îngeraş, rătăcit respectiv fericit), numărul de morcovi ronţăiţi până în momentul terminării expediţiei, precum şi numărul de paşi pe care îi face iepuraşul până la acest moment.
Date de intrare
Pe prima linie a fişierului de intrare iepuras1.in se găsesc două numere întregi m şi n, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale hărţii.
Linia a doua a fişierului conţine trei numere naturale, separate prin câte un spaţiu, reprezentând linia si coloana poziţiei iniţiale a iepuraşului pe hartă precum şi direcţia spre care acesta este orientat. Direcţia este codificată astfel: 1 pentru nord, 2 pentru vest, 3 pentru sud, 4 pentru est.
Următoarele m linii conţin câte n numere întregi separate prin câte un spaţiu, reprezentând codificarea hărţii grădinii, conform celor precizate mai sus.
Următoarea linie conţine un singur număr natural t reprezentând numărul de celule ce vor conţine ziduri după prima trecere printr-o celulă conţinând o trapă. Următoarele t linii conţin câte două numere naturale i şi j, separate printr-un spaţiu, reprezentând coordonatele câte unei celule ce va conţine zid după o primă trecere printr-o celulă conţinând o trapă.
Date de ieșire
Fişierul de ieşire iepuras1.out va conţine pe prima sa linie unul dintre cuvintele INGERAS, RATACIT respectiv FERICIT, corespunzător stării finale a iepuraşului. A doua linie a fişierului va conţine două numere întregi separate printr-un spaţiu, reprezentând linia şi coloana ultimei poziţii de pe teren a iepuraşului, adică poziţia în care a murit, sau în care a devenit fericit, respectiv ultima poziţie a sa de pe teren, înainte de a se rătăci.
A treia linie a fişierului va conţine două numere întregi separate printr-un spaţiu, reprezentând numărul de morcovi culeşi până în momentul terminării expediţiei, respectiv numărul de paşi pe care îi face iepuraşul până ajunge în starea finală.
Restricții și precizări
- poziţia iniţială a iepuraşului este una validă, adică este o celulă liberă din interiorul terenului;
- pentru datele de test, se asigură că iepuraşul va face un număr finit de paşi până la terminarea expediţiei sale;
1 ≤ m, n ≤ 2000 ≤ t ≤ 20- numărul maxim de ziduri aflate la un moment dat pe teren este de cel mult 50, şi este posibil ca la un moment dat să nu existe niciun zid pe teren.
- Se garantează că pentru datele de intrare iepuraşul nu poate ajunge simultan în două din cele trei stări.
- Pomii şi trapele sunt obiecte care rămân permanent în teren, în poziţiile lor iniţiale.
- Într-o celulă a grădinii se poate găsi la un moment dat o singură surpriză (
pom,zid,trapă,morcov,săgeată,bombă).
Exemplu1:
iepuras1.in
10 15 7 1 4 0 0 6 0 5 5 0 7 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 4 0 0 0 0 0 3 0 5 5 0 5 5 0 0 0 0 0 0 0 0 0 0 5 5 0 5 5 0 1 7 0 0 7 0 0 2 0 0 0 0 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 3 0 0 0 5 6 0 0 5 5 5 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 5 0 0 4 0 0 0 7 0 0 3 5 0 0 0 5 0 0 6 0 0 0 0 0 0 1 5 0 0 0 5 0 0
iepuras1.out
FERICIT 1 8 5 37
def simulare_gradina(m, n, gradina, poz_initiala, directie_initiala):
# Direcțiile de mișcare: nord, vest, sud, est
directii = {
'nord': (-1, 0),
'vest': (0, -1),
'sud': (1, 0),
'est': (0, 1)
}
# Mapare coduri săgeți la direcții
sageata_la_directie = {
1: 'nord',
2: 'vest',
3: 'sud',
4: 'est'
}
# Poziția curentă și direcția curentă
x, y = poz_initiala
directie = directie_initiala
# Contoare
morcovi_ronțăiți = 0
pasi = 0
treceri_pe_langa_bombe = {}
starea_finala = 'rătăcit' # implicit
# Funcție pentru verificarea granițelor
def in_gradina(x, y):
return 0 <= x < m and 0 <= y < n
# Pozițiile inițiale ale zidurilor
ziduri_initiale = set()
for i in range(m):
for j in range(n):
if gradina[i][j] == 8:
ziduri_initiale.add((i, j))
# Pozițiile zidurilor alternative
ziduri_alternative = set()
# Inițial, zidurile sunt cele inițiale
ziduri_curente = ziduri_initiale.copy()
# Traseul iepurașului
while True:
if not in_gradina(x, y):
starea_finala = 'rătăcit'
break
pasi += 1
celula = gradina[x][y]
if celula == 7: # morcov
morcovi_ronțăiți += 1
gradina[x][y] = 0
elif celula in sageata_la_directie: # săgeată
directie = sageata_la_directie[celula]
gradina[x][y] = 0
elif celula == 5: # pom
dx, dy = directii[directie]
x -= dx
y -= dy
directie = {'nord': 'sud', 'sud': 'nord', 'vest': 'est', 'est': 'vest'}[directie]
elif celula == 6: # bombă
starea_finala = 'îngeraș'
break
elif celula == 9: # trapă
ziduri_curente = ziduri_alternative if ziduri_curente == ziduri_initiale else ziduri_initiale
# Verificăm dacă trece pe lângă o bombă
vecini = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
for vx, vy in vecini:
if in_gradina(vx, vy) and gradina[vx][vy] == 6:
if (vx, vy) not in treceri_pe_langa_bombe:
treceri_pe_langa_bombe[(vx, vy)] = 0
treceri_pe_langa_bombe[(vx, vy)] += 1
if treceri_pe_langa_bombe[(vx, vy)] == 2:
starea_finala = 'îngeraș'
return starea_finala, morcovi_ronțăiți, pasi
# Deplasarea iepurașului
dx, dy = directii[directie]
x += dx
y += dy
# Verificăm dacă toate morcovii au fost mâncați
if all(all(cell != 7 for cell in row) for row in gradina):
starea_finala = 'fericit'
break
return starea_finala, morcovi_ronțăiți, pasi
# Exemplu de utilizare
m = 4
n = 4
gradina = [
[0, 7, 0, 0],
[2, 5, 3, 0],
[0, 6, 0, 7],
[0, 0, 0, 0]
]
poz_initiala = (0, 0)
directie_initiala = 'est'
rezultat = simulare_gradina(m, n, gradina, poz_initiala, directie_initiala)
print(rezultat)
