1699 - Robotel

Tudor a primit un joc educaţional numit “Roboţel” cu ajutorul căruia va învăţa punctele cardinale Nord, Est, Sud, Vest. Jocul constă dintr-un roboţel care se deplasează pe o tablă de forma unei matrici pătratice, împărţită în R linii şi R coloane. Fiecare căsuţă, aflată la intersecţia dintre o linie şi o coloană, este fie căsuță „liberă”, fie căsuță „semnalizator”, caz în care este etichetată cu una din literele N, E, S, V, reprezentând 4 sensuri posibile de deplasare. Când roboțelul ajunge într-o „căsuţă semnalizator”, el îşi schimbă sensul de deplasare astfel:

• Dacă căsuţa este etichetată cu N atunci roboţelul se va deplasa în continuare de jos în sus;
• Dacă căsuţa este etichetată cu E atunci roboţelul se va deplasa în continuare de la stânga la dreapta;
• Dacă căsuţa este etichetată cu S atunci roboţelul se va deplasa în continuare de sus în jos;
• Dacă căsuţa este etichetată cu V atunci roboţelul se va deplasa în continuare de la dreapta la stânga.

Două căsuțe semnalizator formează o pereche „blocantă” dacă:

• Se află pe aceeași linie și conțin literele E și V, căsuța cu E are coloana mai mică decât a celei etichetate cu V și între ele, pe aceeași linie nu există alte căsuțe semnalizatoare.
• Se află pe aceeași coloană și conțin literele S și N, căsuța cu S are linia mai mică decât a celei etichetate cu N și între ele, pe aceeași coloană nu există alte căsuțe semnalizatoare.

În figura 1, de exemplu, sunt 2 perechi blocante: Perechea (1,2) (5.2) și perechea (2,3) (2,5).

Roboţelul porneşte din căsuţa (1,1), aflată pe prima linie și prima coloană şi dacă aceasta este liberă, se deplasează, în cadrul primei linii, de la stânga la dreapta. În cazul în care căsuța de pornire (1,1) este semnalizator, atunci roboțelul se va deplasa pe direcția indicată de litera cu care este etichetată. Considerând că roboțelul se deplasează pe tablă, el se oprește doar în următoarele situații:

• Roboţelul intră într-o căsuţă liberă aflată pe prima sau ultima linie, respectiv prima sau ultima coloană, caz în care dacă s-ar menține sensul deplasării actuale roboțelul ar părăsi tabla;
• Roboțelul intră într-o „căsuţă semnalizator” a unei perechi blocantă și se va opri în cealaltă căsuță a perechii.

De exemplu, în Figura 2, roboțelul ajunge în căsuța liberă (3,5) unde se oprește. În Figura 3, roboțelul se va opri în căsuța (4,1) deoarece dacă ar schimba sensul spre Est, ar reveni în ultima căsuță semnalizator vizitată, (4,3).

Roboțelul înaintează o căsuță într-un pas, în sensul de deplasare.

Cerința

Scrieţi un program care, cunoscând numărul R de linii şi coloane și cele K căsuţe semnalizator, determină:

1. Toate perechile blocante de pe tablă;
2. Numărul de pași efectuați pe fiecare sens în parte: Nord, Est, Sud și Vest

Date de intrare

Fișierul de intrare robotel.in conține pe prima linie numărul natural P reprezentând cerința din problemă care trebuie rezolvată, pe a doua linie, separate printr-un spaţiu numărul natural R şi numărul natural K, iar pe următoarele K linii, două numere naturale și un caracter, separate prin câte un spațiu reprezentând, în ordine, linia, coloana şi litera unei căsuţe semnalizator.

Date de ieșire

Dacă valoarea lui P este 1, se va rezolva doar cerința 1). Fişierul de ieşire robotel.out va conține perechile blocante, pentru fiecare pereche de căsuțe afișându-se 4 numere naturale separate printr-un spaţiu, reprezentând, în ordine, linia, coloana primei căsuțe semnalizator, respectiv linia și coloana celei de-a doua căsuțe semnalizator. Perechile de căsuțe vor fi afișate pe linii ordonat după regula: o pereche L1 C1 L2 C2 va fi afișată înaintea perechii L3 C3 L4 C4 dacă L1<L3 sau L1=L3 și C1<C3, adică se va afișa mai întâi perechea cu prima căsuță având linia mai mică decât a primei căsuțe din cealaltă pereche sau la linii egale, va fi afișată perechea cu coloana mai mică. Dacă nu există astfel de perechi de căsuțe, în fișierul de ieșire se va afișa valoarea 0.

Dacă valoarea lui P este 2, se va rezolva doar cerința 2). Fişierul de ieşire robotel.out va conţine 4 numere naturale separate printr-un spaţiu, reprezentând, în ordine, numărul de pași parcurși de roboţel în sensurile Nord, Est, Sud, și Vest.

Restricții și precizări

• 2 ≤ R ≤ 200 și 1 ≤ K ≤ R*R
• Pentru rezolvarea corectă a fiecărei cerinţe se obțin câte 50 de puncte
• O căsuță semnalizator conține o singură literă
• Pentru cerința 2 se garantează că în toate testele deplasarea roboțelului se oprește!

Exemplu

robotel.in

1
5 4
1 3 S
3 1 E
5 1 N
5 3 V

robotel.out

0

Explicație

Nu există perechi blocante pe tablă care ar putea opri roboţelul.

def find_blocking_pairs(R, semnalizatori):
    # Găsirea perechilor blocante
    perechi_blocante = []
    
    # Parcurgerea liniilor pentru perechi E-V
    for i in range(R):
        e_index = -1
        for j in range(R):
            if (i, j) in semnalizatori and semnalizatori[(i, j)] == 'E':
                e_index = j
            elif (i, j) in semnalizatori and semnalizatori[(i, j)] == 'V':
                if e_index != -1:
                    perechi_blocante.append(((i, e_index), (i, j)))
                    e_index = -1  # Resetăm indexul pentru următoarea pereche

    # Parcurgerea coloanelor pentru perechi S-N
    for j in range(R):
        s_index = -1
        for i in range(R):
            if (i, j) in semnalizatori and semnalizatori[(i, j)] == 'S':
                s_index = i
            elif (i, j) in semnalizatori and semnalizatori[(i, j)] == 'N':
                if s_index != -1:
                    perechi_blocante.append(((s_index, j), (i, j)))
                    s_index = -1  # Resetăm indexul pentru următoarea pereche
    
    return perechi_blocante

def simulate_robot(R, semnalizatori, perechi_blocante):
    # Direcțiile Nord, Est, Sud, Vest
    directions = {'N': (-1, 0), 'E': (0, 1), 'S': (1, 0), 'V': (0, -1)}
    steps_count = {'N': 0, 'E': 0, 'S': 0, 'V': 0}
    
    # Poziția inițială și direcția inițială
    x, y = 0, 0
    direction = 'E'
    
    visited = set()
    
    while True:
        # Marcați poziția curentă ca vizitată
        visited.add((x, y))
        
        # Verificați dacă poziția curentă este o căsuță semnalizator
        if (x, y) in semnalizatori:
            direction = semnalizatori[(x, y)]
        
        # Calculați următoarea poziție
        dx, dy = directions[direction]
        new_x, new_y = x + dx, y + dy
        
        # Verificați dacă următoarea poziție este în afara grilei
        if not (0 <= new_x < R and 0 <= new_y < R):
            break
        
        # Verificați dacă se întâlnește o pereche blocantă
        for (ax, ay), (bx, by) in perechi_blocante:
            if (x, y) == (ax, ay) and (new_x, new_y) == (bx, by):
                x, y = bx, by
                break
            elif (x, y) == (bx, by) and (new_x, new_y) == (ax, ay):
                x, y = ax, ay
                break
        else:
            # Dacă nu se întâlnește o pereche blocantă, actualizați poziția
            x, y = new_x, new_y
        
        # Incrementați contorul de pași pentru direcția curentă
        steps_count[direction] += 1
    
    return steps_count

# Exemplu de utilizare
R = 5
semnalizatori = {
    (0, 1): 'E', (4, 1): 'V',  # Pereche blocantă (0,1) (4,1)
    (1, 2): 'S', (1, 4): 'N',  # Pereche blocantă (1,2) (1,4)
    (3, 2): 'N', (4, 2): 'S',  # Nu formează pereche blocantă
}
perechi_blocante = find_blocking_pairs(R, semnalizatori)
steps_count = simulate_robot(R, semnalizatori, perechi_blocante)

print(f"Perechi blocante: {perechi_blocante}")
print(f"Numărul de pași în fiecare direcție: {steps_count}")