Cod sursa(job #2788876)

Utilizator Giani26Visalon Giani Giani26 Data 26 octombrie 2021 16:50:03
Problema Rj Scor 0
Compilator py Status done
Runda Arhiva de probleme Marime 6.83 kb
import collections
def drum(nume_fisier):
    f=open(nume_fisier)
    ls=f.readline()
    l=[int(x) for x in ls.split()]
    n=l[0]
    m=l[1]
    xr=0
    yr=0
    xj=0
    yj=0
    a=[[0 for i in range(n+1)]for j  in range(m+1)]
    for i in range(m):
        ls=f.readline()
        l=ls.strip()
        for j in range(len(l)):
            if(l[j]=='R'):
                xr=i+1
                yr=j+1
            else:
                if(l[j]=='X'):
                    a[i+1][j+1]=1
                else:
                    if(l[j]=='J'):
                        xj=i+1
                        yj=j+1
    return a,xr,yr,xj,yj,n,m

def BFS(x,y,n,m,a):
    de1 = collections.deque()

    x1=0
    y1=0
    viz = [[0 for i in range(n + 1)] for j in range(m + 1)]
    viz[x][y] = 1
    d = [[0 for i in range(n + 1)] for j in range(m + 1)]
    de1.append((x,y))

    while de1:
        u=de1.popleft()
        x1=int(u[0])
        y1=int(u[1])

        if(x1>1 and x1<m and y1>1 and y1<n):
            if(viz[x1+1][y1]==0 and a[x1+1][y1]!=1):
                viz[x1+1][y1]=1
                d[x1+1][y1]=d[x1][y1]+1
                de1.append((x1+1,y1))
            if (viz[x1 - 1][y1] == 0 and  a[x1-1][y1]!=1):
                viz[x1 - 1][y1] = 1
                d[x1 - 1][y1] = d[x1][y1] + 1
                de1.append((x1 - 1, y1))
            if (viz[x1 ][y1+1] == 0 and a[x1][y1+1]!=1):
                viz[x1 ][y1+1] = 1
                d[x1 ][y1+1] = d[x1][y1] + 1
                de1.append((x1 , y1+1))
            if (viz[x1 ][y1-1] == 0 and a[x1][y1-1]!=1):
                viz[x1 ][y1-1] = 1
                d[x1][y1-1] = d[x1][y1] + 1
                de1.append((x1, y1-1))


        if(x1==1):
                if(y1==1):
                    if (viz[x1 + 1][y1] == 0 and a[x1+1][y1]==0):
                        viz[x1 + 1][y1] = 1
                        d[x1 + 1][y1] = d[x1][y1] + 1
                        de1.append((x1 + 1, y1))
                    if (viz[x1][y1 + 1] == 0 and a[x1][y1+1]==0):
                        viz[x1][y1 + 1] = 1
                        d[x1][y1 + 1] = d[x1][y1] + 1
                        de1.append((x1 , y1+1))




                if(y1==n):
                        if (viz[x1][y1 - 1] == 0 and a[x1][y1-1]==0):
                            viz[x1][y1 - 1] = 1
                            d[x1][y1 - 1] = d[x1][y1] + 1
                            de1.append((x1, y1 - 1))
                        if (viz[x1 + 1][y1] == 0 and a[x1+1][y1]==0):
                            viz[x1 + 1][y1] = 1
                            d[x1 + 1][y1] = d[x1][y1] + 1
                            de1.append((x1 + 1, y1))


                if (y1 > 1 and y1 < n):
                            if (viz[x1][y1 - 1] == 0 and a[x1][y1-1]==0):
                                viz[x1][y1 - 1] = 1
                                d[x1][y1 - 1] = d[x1][y1] + 1
                                de1.append((x1, y1 - 1))
                            if (viz[x1][y1 + 1] == 0 and a[x1][y1+1]==0):
                                viz[x1][y1 + 1] = 1
                                d[x1][y1 + 1] = d[x1][y1] + 1
                                de1.append((x1, y1 + 1))
                            if (viz[x1 + 1][y1] == 0 and a[x1+1][y1]==0):
                                viz[x1 + 1][y1] = 1
                                d[x1 + 1][y1] = d[x1][y1] + 1
                                de1.append((x1 + 1, y1))



        if(x1==m):
                    if (y1 == 1):

                        if (viz[x1 - 1][y1] == 0 and a[x1-1][y1]==0):
                            viz[x1 - 1][y1] = 1
                            d[x1 - 1][y1] = d[x1][y1] + 1
                            de1.append((x1 - 1, y1))
                        if (viz[x1][y1 + 1] == 0 and a[x1][y1+1]==0) :
                                viz[x1][y1 + 1] = 1
                                d[x1][y1 + 1] = d[x1][y1] + 1
                                de1.append((x1, y1 + 1))


                    if(y1==n):
                            if (viz[x1 - 1][y1] == 0 and a[x1 - 1][y1] ==0):
                                viz[x1 - 1][y1] = 1
                                d[x1 - 1][y1] = d[x1][y1] + 1
                                de1.append((x1 - 1, y1))
                            if (viz[x1][y1 - 1] == 0 and a[x1][y1-1]==0):
                                viz[x1][y1 - 1] = 1
                                d[x1][y1 - 1] = d[x1][y1] + 1
                                de1.append((x1, y1 - 1))

                    if (y1 > 1 and y1 < n):
                        if (viz[x1][y1 - 1] == 0 and a[x1 ][y1 - 1] ==0):
                            viz[x1][y1 - 1] = 1
                            d[x1][y1 - 1] = d[x1][y1] + 1
                            de1.append((x1, y1 - 1))
                        if (viz[x1][y1 + 1] == 0 and a[x1 ][y1 + 1] ==0):
                            viz[x1][y1 + 1] = 1
                            d[x1][y1 + 1] = d[x1][y1] + 1
                            de1.append((x1,y1+1))
                        if (viz[x1 - 1][y1] == 0 and a[x1 - 1][y1] ==0):
                            viz[x1 - 1][y1] = 1
                            d[x1 - 1][y1] = d[x1][y1] + 1
                            de1.append((x1 - 1, y1))


        if (x1 > 1 and x1 < m):
            if (y1 == 1):
                if (viz[x1 - 1][y1] == 0 and a[x1 - 1][y1 ] ==0):
                    viz[x1 - 1][y1] = 1
                    d[x1 - 1][y1] = d[x1][y1] + 1
                    de1.append((x1 - 1, y1))
                if (viz[x1][y1 + 1] == 0 and a[x1 ][y1 + 1] ==0):
                    viz[x1][y1 + 1] = 1
                    d[x1][y1 + 1] = d[x1][y1] + 1
                    de1.append((x1, y1 + 1))
                if (viz[x1 + 1][y1] == 0)and a[x1 +1][y1 ] ==0:
                    viz[x1 + 1][y1] = 1
                    d[x1 + 1][y1] = d[x1][y1] + 1
                    de1.append((x1 + 1, y1))



            else:
                if (y1 == n):
                    if (viz[x1 - 1][y1] == 0 and a[x1 - 1][y1 ] ==0):
                        viz[x1 - 1][y1] = 1
                        d[x1 - 1][y1] = d[x1][y1] + 1
                        de1.append((x1 - 1, y1))



                    if (viz[x1 + 1][y1] == 0 and a[x1 + 1][y1] == 0):
                        viz[x1 + 1][y1] = 1
                        d[x1 + 1][y1] = d[x1][y1] + 1
                        de1.append((x1 + 1, y1))
                    if (viz[x1][y1 - 1] == 0 and a[x1][y1 - 1] != 1):
                        viz[x1][y1 - 1] = 1
                        d[x1][y1 - 1] = d[x1][y1] + 1
                        de1.append((x1, y1 - 1))


    return d
a,xr,yr,xj,yj,n,m=drum('julieta.in')

d=BFS(xj,yj,n,m,a)

p=BFS(xr,yr,n,m,a)
for i in range(1,n+1):
    for j in range(1,n+1):
        if(d[i][j]==p[i][j] and p[i][j]!=0):
            print(d[i][j],i,j)