Editing 0880 - Soarece (section)

== Rezolvare ==
<syntaxhighlight lang="python" line>
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()


</syntaxhighlight>