2101 - Traseu2

Enunț

Fie un labirint reprezentat ca o matrice pătratică cu n linii (numerotate de sus în jos de la 1 la n) şi n coloane (numerotate de la stânga la dreapta de la 1 la n). Elementele matricei pot fi 0 (semnificând culoar de trecere) sau 1 (semnificând zid). Un roboţel se mişcă prin labirint după un anumit traseu, specificat ca o succesiune de direcţii de mişcare. Direcţiile pot fi:

• N (nord), adică din poziţia curentă (x,y) robotul se deplasează în poziţia (x-1,y), dacă nu este zid;
• S (sud), adică din poziţia curentă (x,y) robotul se deplasează în poziţia (x+1,y), dacă nu este zid;
• E (est), adică din poziţia curentă (x,y) robotul se deplasează în poziţia (x,y+1), dacă nu este zid;
• V (vest), adică din poziţia curentă (x,y) robotul se deplasează în poziţia (x,y-1), dacă nu este zid;

Observaţi că roboţelul nu poate trece prin ziduri, prin urmare, dacă în direcţia de mişcare curentă se află un zid, el nu va efectua deplasarea respectivă.

Cerința

Dată fiind configuraţia labirintului, poziţia iniţială a roboţelului şi traseul pe care se deplasează acesta, să se determine poziţia finală a robotului.

Date de intrare

Fişierul de intrare traseu2in.txt conţine pe prima linie numărul natural n, reprezentând dimensiunea labirintului. Pe cea de a doua linie sunt scrise două numere naturale L C (cuprinse între 1 şi n), reprezentând poziţia iniţială a roboţelului (L fiind linia, iar C fiind coloana). Pe următoarele n linii se află câte n valori din mulţimea {0,1}, reprezentând configuraţia labirintului. Pe ultima linie se află un şir de caractere din mulţimea {′N′, ′S′, ′E′, ′V′}, reprezentând traseul roboţelului.

Date de ieșire

Fişierul de ieşire traseu2out.txt va conţine o singură linie pe care vor fi scrise două numere naturale cuprinse între 1 şi n reprezentând linia, respectiv coloana poziţiei în care se află roboţelul după parcurgerea traseului. Dacă în timpul deplasării pe traseu roboţelul părăseşte labirintul, pe prima linie vor fi scrise linia, respectiv coloana ultimei poziţii pe care a avut-o roboţelul în labirint.

Restricții și precizări

• 1 ⩽ n ⩽ 100
• Traseul are lungimea ⩽ 250
• Valorile numerice scrise pe aceeaşi linie în fişierul de intrare şi în fişierul de ieşire vor fi separate prin câte un spaţiu.
• Poziţia iniţială a roboţelului se află pe culoar.

Exemplul 1

Intrare

traseu2in.txt

5

2 1

1 0 0 0 1

0 0 1 0 1

1 0 0 0 0

1 0 0 1 1

1 1 0 0 0

ENESES

Ieșire

Datele de intrare corespund restricțiilor impuse

traseu2out.txt

2 4

Explicație

Din poziţia (2,1) roboţelul face o deplasare spre Est şi ajunge în poziţia (2,2). Următoarea deplasare este spre Nord şi ajunge în poziţia (1,2). Următoarea deplasare este spre Est şi ajunge în poziţia (1,3). Următoarea deplasare ar fi trebuit să fie spre Sud, dar aceasta nu poate fi efectuată, fiindcă la sud este zid. Următoarea deplasare este spre Est şi ajunge în (1,4), apoi la Sud, şi ajunge în (2,4).

Exemplul 2

Intrare

traseu2in.txt

3

2 2

1 0 0

0 0 1

1 0 0

VVV

Ieșire

Datele de intrare corespund restricțiilor impuse

traseu2out.txt

2 1

Explicație

Din poziţia (2,2) roboţelul se deplasează spre Vest, ajunge în poziţia (2,1). La următoarea deplasare spre Vest, roboţelul părăseşte labirintul.

Exemplul 3

Intrare

traseu2in.txt

0

2 1

1 0 0 0 1

0 0 1 0 1

1 0 0 0 0

1 0 0 1 1

1 1 0 0 0

ENESES

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#2101 - Traseu2

def validare_date(n, l, c, labirint, traseu):
    if not (1 <= n <= 100):
        return False
    if not (1 <= l <= n) or not (1 <= c <= n):
        return False
    if len(labirint) != n or any(len(row) != n for row in labirint):
        return False
    if len(traseu) > 250:
        return False
    return True


def determina_pozitie_finala(n, l, c, labirint, traseu):
    directii = {'N': (-1, 0), 'S': (1, 0), 'E': (0, 1), 'V': (0, -1)}

    x, y = l - 1, c - 1

    for directie in traseu:
        dx, dy = directii[directie]
        nx, ny = x + dx, y + dy

        if 0 <= nx < n and 0 <= ny < n and labirint[nx][ny] == 0:
            x, y = nx, ny

    return x + 1, y + 1


def main():
    with open("traseu2in.txt", "r") as fin:
        n = int(fin.readline().strip())
        l, c = map(int, fin.readline().split())
        labirint = [list(map(int, fin.readline().split())) for _ in range(n)]
        traseu = fin.readline().strip()

    if validare_date(n, l, c, labirint, traseu):
        print("Datele de intrare corespund restricțiilor impuse")

        rezultat = determina_pozitie_finala(n, l, c, labirint, traseu)

        with open("traseu2out.txt", "w") as fout:
            fout.write(f"{rezultat[0]} {rezultat[1]}\n")
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)


if __name__ == "__main__":
    main()