Editing 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 <code>m</code> linii, numerotate de la <code>1</code> la <code>m</code> de sus în jos, şi <code>n</code> coloane, numerotate de la <code>1</code> la <code>n</code> 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 <code>săgeată spre nord</code>, '''2''' pentru <code>săgeată spre vest</code>, '''3''' pentru <code>săgeată spre sud</code>, '''4''' pentru <code>săgeată spre est</code>, '''5''' pentru <code>pom</code>, '''6''' pentru <code>bombă</code>, '''7''' pentru <code>morcov</code>, '''8''' pentru <code>zid</code>, '''9''' pentru <code>trapă</code>. <code>Căsuţele libere</code> 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 <code>iepuras1.in</code> se găsesc două numere întregi <code>m</code> şi <code>n</code>, 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 <code>nord</code>, '''2''' pentru <code>vest</code>, '''3''' pentru <code>sud</code>, '''4''' pentru <code>est</code>.

Următoarele m linii conţin câte <code>n</code> 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 <code>t</code> reprezentând numărul de celule ce vor conţine ziduri după prima trecere printr-o celulă conţinând o trapă. Următoarele <code>t</code> linii conţin câte două numere naturale <code>i</code> şi <code>j</code>, 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 <code>iepuras1.out</code> va conţine pe prima sa linie unul dintre cuvintele <code>INGERAS</code>, <code>RATACIT</code> respectiv <code>FERICIT</code>, 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;
* <code>1 ≤ m, n ≤ 200</code>
* <code>0 ≤ t ≤ 20</code>
* 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ă (<code>pom</code>, <code>zid</code>, <code>trapă</code>, <code>morcov</code>, <code>săgeată</code>, <code>bombă</code>).

= Exemplu1: =
<code>iepuras1.in</code>
 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 
<code>iepuras1.out</code>
 FERICIT
 1 8
 5 37
<syntaxhighlight lang="python" line="1">
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)
</syntaxhighlight>