2341 - Labirint 4

Cerința

Cătălin s-a pierdut iarăși într-o matrice de N linii și M coloane în care unele celule sunt blocate. Cătălin nu găsește ieșirea așa că s-a decis să caute o comoară. El are o harta pe care a desenat-o când era mic și decide să o urmeze. Pe harta este scris un șir format din caracterele U, R, D, L. În fiecare secundă Cătălin se va deplasa în una dintre cele 4 celule adiacente. Presupunând că la secunda S Cătălin se află în celula i, j el se va mișcă în funcție de al S-lea caracter de pe harta în felul următor: pentru U el va păși în celula i - 1, j; pentru R el va păși în celula i, j + 1; pentru D el va păși în celula i + 1, j, iar pentru L, el va păși în celula i, j - 1.

Dacă celula în care trebuie să pășească este în afara matricei sau este blocată, atunci Cătălin va sta pe loc în acea secunda. În ce celulă ajunge Cătălin?

Date de intrare

Pe prima linie a fișierului de intrare labirint4in.txt se vor afla trei numere naturale N, M și K. Pe următoarele K linii se vor afla cate 2 numere reprezentând linia și coloana unei celule blocate. Pe următoarea linie se vor afla 2 numere naturale reprezentând linia, respectiv coloana de pe care începe Cătălin să se miște. Pe ultima linie se va afla numărul de caractere din șirul de pe hartă urmat de acele caractere.

Date de ieșire

În fișierul de ieșire​ labirint4out.txt​ se vor afla două numere reprezentând linia și coloana pe care ajunge Cătălin.

Restricții și precizări

• 1 ⩽ lungimea șirului de pe hartă ⩽ 10.000
• 1 ⩽ n, m ⩽ 10.000 și k = 0
• 1 ⩽ n, m ⩽ 500 și 1 ⩽ k ⩽ n*m
• 1 ⩽ n, m ⩽ 10.000 și 1 ⩽ k ⩽ 1.000

Exemplul 1

Intrare

labirint4in.txt

4 5 7

1 3

1 5

2 1

2 4

2 5

3 1

3 2

2 2

11

ULRDDRDRDLU

Ieșire

Datele de intrare corespund restricțiilor impuse

labirint4out.txt

3 3

Explicație

Traseul lui Catalin este: (2, 2) → (1, 2) → (1, 1) → (1, 2) → (2, 2) → (2, 3) → (3, 3) → (3, 4) → (4, 4) → (4, 3) → (3, 3)

Exemplul 2

Intrare

labirint4in.txt

10001 5 7

1 3

1 5

2 1

2 4

2 5

3 1

3 2

2 2

11

ULRDDRDRDLU

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#2341 - Labirint4

def este_valid(n, m, k, celule_blocate, start, lungime_harta):
    if not (1 <= lungime_harta <= 10000):
        return False

    if not (1 <= n <= 10000) or not (1 <= m <= 10000):
        return False

    if not (0 <= k <= n * m):
        return False

    for i, j in celule_blocate:
        if not (1 <= i <= n) or not (1 <= j <= m):
            return False

    if not (1 <= start[0] <= n) or not (1 <= start[1] <= m):
        return False

    return True


def este_in_matrice(i, j, n, m):
    return 1 <= i <= n and 1 <= j <= m


def rezolva_labirint(n, m, celule_blocate, start, lungime_harta, harta):
    directii = {'U': (-1, 0), 'R': (0, 1), 'D': (1, 0), 'L': (0, -1)}

    i, j = start
    for s in range(lungime_harta):
        directie = harta[s]
        di, dj = directii[directie]
        i_nou, j_nou = i + di, j + dj

        if este_in_matrice(i_nou, j_nou, n, m) and (i_nou, j_nou) not in celule_blocate:
            i, j = i_nou, j_nou

    return i, j


def main():
    with open("labirint4in.txt", "r") as f:
        n, m, k = map(int, f.readline().split())
        celule_blocate = [tuple(map(int, f.readline().split())) for _ in range(k)]
        start = tuple(map(int, f.readline().split()))
        lungime_harta = int(f.readline())
        harta = f.readline().strip()

    if este_valid(n, m, k, celule_blocate, start, lungime_harta):
        print("Datele de intrare corespund restricțiilor impuse")
        rezultat = rezolva_labirint(n, m, celule_blocate, start, lungime_harta, harta)

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


if __name__ == "__main__":
    main()