Editing 0868 - Acces1 (section)

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque


def validare(n_linii, m_coloane, matrice):
    if n_linii > 1000 or m_coloane > 1000:
        raise ValueError
    for linie in matrice:
        for caracter in linie:
            if caracter not in ['-', '#', 'P']:
                raise ValueError


def bfs(n_linii, m_coloane, matrice):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    distanta = [[-1] * m_coloane for _ in range(n_linii)]
    q = deque()

    for nr_i in range(n_linii):
        for nr_j in range(m_coloane):
            if matrice[nr_i][nr_j] == 'P':
                q.append((nr_i, nr_j))
                distanta[nr_i][nr_j] = 0

    while q:
        x, y = q.popleft()
        for directie in range(4):
            nx, ny = x + dx[directie], y + dy[directie]
            if 0 <= nx < n_linii and 0 <= ny < m_coloane and matrice[nx][ny] != '#' and distanta[nx][ny] == -1:
                distanta[nx][ny] = distanta[x][y] + 1
                q.append((nx, ny))

    return distanta


if __name__ == '__main__':
    file_in = open("acces1in.txt", "r")
    file_out = open("acces1out.txt", "w")

    try:
        n, m = map(int, file_in.readline().split())
        mat = [list(file_in.readline().strip()) for _ in range(n)]

        validare(n, m, mat)
        file_out.write("Datele de intrare corespund restrictiilor impuse\n")
        dist = bfs(n, m, mat)

        for i in range(n):
            for j in range(m):
                if mat[i][j] == '#':
                    file_out.write('# ')
                elif dist[i][j] == -1:
                    file_out.write('- ')
                else:
                    file_out.write(str(dist[i][j]) + ' ')
            file_out.write('\n')

    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>