Cod sursa(job #2665997)

Utilizator MicuMicuda Andrei Micu Data 31 octombrie 2020 17:04:19
Problema Rj Scor 0
Compilator py Status done
Runda Arhiva de probleme Marime 1.59 kb
import queue


ox = [-1, 0, 1, -1, 1, -1, 0, 1]

oy = [-1, -1, -1, 0, 0, 1, 1, 1]


def isValid(pos, matPos, matLen):

    global n, m

    i = pos[0]

    j = pos[1]

    if i < 0 or j < 0 or i >= n or j >= m:

        return False

    if matPos[i][j] == 'X' or matLen[i][j] != -1:

        return False

    return True


def lee(matPos, matLen, root):

    global ox, oy

    q = queue.Queue()

    matLen[root[0]][root[1]] = 0

    q.put(root)

    while q.qsize() > 0:

        curr_pos = q.get()

        for i in range(8):

            next_pos = (curr_pos[0] + ox[i], curr_pos[1] + oy[i])

            if isValid(next_pos, matPos, matLen):

                matLen[next_pos[0]][next_pos[1]

                                    ] = matLen[curr_pos[0]][curr_pos[1]] + 1

                q.put(next_pos)


with open("rj.in", 'r') as fin:
    tmp = fin.readline().split()
    n = int(tmp[0])
    m = int(tmp[1])
    mat = [[0] * m for _ in range(n)]
    mat1 = [[-1] * m for _ in range(n)]
    mat2 = [[-1] * m for _ in range(n)]

    mat = fin.readlines()

    for i in range(n):
        for j in range(m):
            if mat[i][j] == 'R':
                root1 = (i, j)

            elif mat[i][j] == 'J':
                root2 = (i, j)


lee(mat, mat1, root1)
lee(mat, mat2, root2)

rez_len = 10e5

for i in range(n):
    for j in range(m):
        if mat1[i][j] == mat2[i][j] and mat1[i][j] != -1:
            if mat1[i][j] < rez_len:
                rez_len = mat1[i][j]
                rez_pos = (i+1, j+1)


with open("rj.out", 'w') as fout:
    fout.write(" ".join(str(x) for x in [rez_len+1, rez_pos[0], rez_pos[1]]))