Cod sursa(job #2691258)

Utilizator vvrr24vvrr24 vvrr24 Data 27 decembrie 2020 18:30:09
Problema Rj Scor 0
Compilator py Status done
Runda Arhiva de probleme Marime 2.53 kb
from collections import deque
def citire( nume_fisier ="rj.in"):
    f = open(nume_fisier,"r")
    linie = f.readline()
    n, m = map(int, linie.split())
    lin1 = [ x for x in f.readline()]

    lista = [[] for i in range(m * n)]  # lista adicenta
    i=0
    for j in range(m):
        if lin1[j] == 'R':
            romeo = (i, j)
        if lin1[j] == 'J':
            julieta = (i, j)
        if lin1[j]  in " JR":
            if j > 0 and lin1[j - 1] in " JR":
                lista[m * i + j].append(j - 1)
            if j < m - 1 and lin1[j + 1] in " JR":
                lista[m * i + j].append(j + 1)

    for linie in f:
        i = i+1
        lin2 = [x for x in linie]

        for j in range(m):
            if lin2[j] == 'R':
                romeo = (i,j)
            if lin2[j] == 'J':
                julieta = (i, j)
            if lin2[j] in " JR":

                if j > 0 and lin2[j-1] in " JR":
                    lista[m*i+j].append(m*i+j-1)
                if j < m-1 and lin2[j+1]in " JR":
                    lista[m*i+j].append(m*i+j+1)
                if lin1[j] in " JR":
                    lista[m*i+j].append(m*(i-1)+j)
                    lista[m*(i-1)+j].append(m*i+j)
                if j > 0 and lin1[j-1] in " JR":
                    lista[m*i+j].append(m*(i-1)+j-1)
                    lista[m*(i-1)+j-1].append(m*i+j)
                if j < m-1 and lin1[j+1] in " JR":
                    lista[m*i+j].append(m*(i-1)+j+1)
                    lista[m*(i-1)+j+1].append(m*i+j)
        lin1 = lin2.copy()


    return n,m, lista, romeo, julieta

n,m,lista, romeo, julieta = citire()

def minim_romeo_julieta( n,m, lista, romeo, julieta):
    viz = [0]*(m*n)
    dist =[0]*(m*n)
    tata = [None] * (m * n)
    q = deque([])
    start = romeo[0] *m + romeo[1]
    final = julieta[0]*m +julieta[1]
    q.append(start)
    viz[start] = 1
    dist[start] = 0
    while q != deque([]):
        i = q.popleft()
        if i == final and dist[i] % 2 == 0:
            break
        else:
            for j in lista[i]:
                if viz[j] == 0:
                    q.append(j)
                    viz[j] = 1
                    tata[j] = i
                    dist[j] = dist[i] + 1
    # in dist[i] vom avea distanta totala
    k=0
    while k <= int(dist[i]//2):
       i = tata[i]
       k += 1
    g = open("rj.out", "w")
    g.write( str(dist[i]+1)+ " " +str( i // m + 1) + " "+str( i % m + 1))
    g.close()



minim_romeo_julieta(n,m,lista, romeo, julieta)