Cod sursa(job #2790209)

Utilizator Mirc100Mircea Octavian Mirc100 Data 28 octombrie 2021 16:41:52
Problema Rj Scor 0
Compilator py Status done
Runda Arhiva de probleme Marime 1.28 kb
import collections
f=open("rj.in")
a=[]
n,m=[int(x) for x in f.readline().split()]

i=0
for linie in f:
    ls=list(linie.rstrip("\n"))
    a.append(ls)
    if 'R' in ls:
        celula_R=(i,ls.index('R'))
    if 'J' in ls:
        celula_J=(i,ls.index('J'))
    i+=1


def in_matrice(x,y):
    return (0<=x<n) and (0<=y<m)



def bfs(celula_start):
    d = [[-1 for i in range(m)] for j in range(n)]
    c=collections.deque()
    c.append(celula_start)
    d[celula_start[0]][celula_start[1]]=0
    depl=[(1,0),(-1,0),(0,1),(0,-1),(1,1), (1,-1), (-1,1),(-1,-1)]
    while len(c)>0:
        x,y = c.popleft() #(x,y) vf curent
        for dir in depl:
            xv=x+dir[0]
            yv=y+dir[1] #vecin (xv,yv)
            if in_matrice(xv,yv) and a[xv][yv]!='X' and d[xv][yv]==-1:
                c.append((xv,yv))
                d[xv][yv] = 1 + d[x][y]

    return d

d_R=bfs(celula_R)
d_J=bfs(celula_J)
"""
for linie in d_R:
    print(linie)
print()
for linie in d_J:
    print(linie)
"""
t_min=m+n

for i in range(n):
    for j in range(m):
        if d_R[i][j]==d_J[i][j] and d_R[i][j]!=-1 and d_R[i][j]<t_min:
            t_min=d_R[i][j]
            celula=(i+1,j+1)
g=open("rj.out","w")
g.write(f"{t_min+1} {celula[0]} {celula[1]}")
g.close()