Pagini recente » Cod sursa (job #1878592) | Cod sursa (job #2777649) | Cod sursa (job #2794838) | Cod sursa (job #2802583) | Cod sursa (job #2691258)
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)