Cod sursa(job #2665984)

Utilizator MicuMicuda Andrei Micu Data 31 octombrie 2020 16:31:06
Problema Rj Scor 0
Compilator py Status done
Runda Arhiva de probleme Marime 1.63 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:
    n, m = [int(x) for x in fin.readline().split()]
    mat = [[-0 for _ in range(5)] for __ in range(5)]
    mat1 = [[-1 for _ in range(5)] for __ in range(5)]
    mat2 = [[-1 for _ in range(5)] for __ in range(5)]
    lines = fin.readlines()

    for i in range(n):
        for j in range(m):
            if lines[i][j] == 'R':
                root1 = (i, j)
            elif lines[i][j] == 'J':
                root2 = (i, j)
            mat[i][j] = lines[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]]))