0880 - Soarece

Cerința

Se dă o tablă dreptunghiulară formată din n linii și m coloane, definind n*m zone, unele dintre ele fiind libere, altele conținând obstacole. Într-o zonă precizată se află un șoarece care se poate deplasa pe tablă trecând din zona curentă în zona învecinată cu aceasta pe linie sau pe coloană. Scopul sau este să ajungă la o bucată de brânză aflată într-o zonă de asemenea precizată, fără a părăsi tabla, fără a trece prin zone care conțin obstacole și fără a trece de două ori prin aceeași zonă.

Determinați o modalitate prin care șoarecele poate să ajungă la bucata de brânză.

Date de intrare

Fişierul de intrare soarece2.in conţine pe prima linie numerele n m, separate printr-un spațiu. Următoarele n linii conțin câte m caractere, care descriu tabla: caracterul _ corespunde unei zone libere, caracterul # corespunde unei zone ocupate de obstacol, caracterul S corespunde zonei în care se află șoarecele iar caracterul B corespunde zonei în care se află bucata de brânză.

Date de ieșire

Fişierul de ieşire soarece2.out va conţine pe prima linie numărul C de deplasări pe care le face șoarecele.

Următoarea linie va conține C caractere din mulțimea {N, E, S, V}, cu următoarea semnificație:

• N – șoarecele se deplasează spre Nord; din zona i j ajunge în zona i - 1 j
• E – șoarecele se deplasează spre Est; din zona i j ajunge în zona i j + 1
• S – șoarecele se deplasează spre Sud; din zona i j ajunge în zona i + 1 j
• V – șoarecele se deplasează spre Vest; din zona i j ajunge în zona i j - 1

Numerele de pe fiecare linie fișierului de ieșire sunt separate prin exact un spațiu.

Restrictii si precizari

• 1 ≤ n, m ≤ 1000
• zona în care se află șoarecele și zona în care se află bucata de brânză sunt libere
• dacă nu există nicio modalitate prin care șoarecele va ajunge la bucata de brânză pe prima linie a fișierului de ieșire se va afla valoarea 0
• oricare traseu valid al șoarecelui este considerat corect

Exemplu 1

Intrare

6 7
_______
_####B_
____##_
S##_#__
_##_#_#
_______

Iesire

9
NNNEEEEES

Rezolvare

from collections import deque

def is_valid_move(n, m, x, y, labirint, vizitat):
    return 0 <= x < n and 0 <= y < m and labirint[x][y] != '#' and not vizitat[x][y]

def gaseste_drum(n, m, labirint, start, branza):
    dx = [-1, 0, 1, 0]  # direcțiile Nord, Est, Sud, Vest
    dy = [0, 1, 0, -1]
    directii = ['N', 'E', 'S', 'V']

    vizitat = [[False] * m for _ in range(n)]
    parinti = [[None] * m for _ in range(n)]
    q = deque([(start[0], start[1])])
    vizitat[start[0]][start[1]] = True

    while q:
        x, y = q.popleft()
        if (x, y) == branza:
            drum = []
            while (x, y) != start:
                px, py = parinti[x][y]
                for i in range(4):
                    if x == px + dx[i] and y == py + dy[i]:
                        drum.append(directii[i])
                        break
                x, y = px, py
            return drum[::-1]
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if is_valid_move(n, m, nx, ny, labirint, vizitat):
                vizitat[nx][ny] = True
                parinti[nx][ny] = (x, y)
                q.append((nx, ny))
    
    return None

def main():
    with open("soarece2.in", "r") as f:
        n, m = map(int, f.readline().strip().split())
        assert 1 <= n <= 1000, "n trebuie să fie între 1 și 1000"
        assert 1 <= m <= 1000, "m trebuie să fie între 1 și 1000"

        labirint = []
        start = None
        branza = None
        
        for i in range(n):
            linie = f.readline().strip()
            assert len(linie) == m, "Fiecare linie trebuie să aibă exact m caractere"
            for j in range(m):
                if linie[j] == 'S':
                    start = (i, j)
                elif linie[j] == 'B':
                    branza = (i, j)
            labirint.append(linie)
        
        assert start is not None, "Trebuie să existe exact un 'S' pentru poziția șoricelului"
        assert branza is not None, "Trebuie să existe exact un 'B' pentru poziția brânzei"
    
    drum = gaseste_drum(n, m, labirint, start, branza)
    
    with open("soarece2.out", "w") as f:
        if drum is None:
            f.write("0\n")
        else:
            f.write(f"{len(drum)}\n")
            f.write("".join(drum) + "\n")

if __name__ == "__main__":
    main()