Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- from sys import stdin
- ##Es el seem_carving de practicas pero MODIFICANDO LA RECONSTRUCCION DEL CAMINO
- ##Recontruir el camino en este problema es una locura.
- def seem_carving(filas,columnas,mapa):
- infty=1e99
- mat = [[infty for x in range(columnas+1)] for y in range(filas+1)]
- backpointers=[[ [] for x in range(columnas+1)] for y in range(filas+1)]
- for x in range(1,filas+1):
- mat[x][0] = infty
- mat[x][1] = mapa[x,1]
- backpointers[x][1]=[x]
- ##Programacion dinamica
- for j in range(2,columnas+1):
- for i in range(1,filas+1):
- iup=i-1
- if iup<=0:
- iup=filas
- idown=i+1
- if idown>filas:
- idown=1
- aux=min(mat[iup][j-1], mat[i][j-1],mat[idown][j-1]) + mapa[i,j]
- mat[i][j]=aux
- prueba=[iup,i,idown]
- posibles=[]
- for q in prueba:
- if mat[i][j]- mapa[i,j]==mat[q][j-1]:
- posibles.append(backpointers[q][j-1]+[i])
- posibles.sort()
- backpointers[i][j]=posibles[0]
- #for i in range(1,filas+1):
- # s=""
- # for j in range(1,columnas+1):
- # s+=str(mapa[i,j])+" "
- # print(s)
- #for i in mat:
- # print(i)
- #for i in backpointers:
- # print(i)
- ##Minval y min_point
- min_val = 1e99
- min_point =-1
- for i in range(1,filas+1):
- if mat[i][columnas] < min_val:
- min_val=mat[i][columnas]
- min_point=i
- coste=mat[min_point][columnas]
- ##PATH
- todos_paths=[]
- for i in range(1,filas+1):
- if mat[i][columnas] ==min_val:
- todos_paths.append(backpointers[i][j])
- todos_paths.sort()
- path=todos_paths[0]
- print(" ".join([str(x) for x in path]))
- print(coste)
- linea=stdin.readline()
- linea.strip()
- while(linea!=''):
- linea=linea.split()
- filas=int(linea[0])
- columnas=int(linea[1])
- nn=filas*columnas
- mapa={}
- nl=0
- i=1
- j=1
- while(nl<nn):
- linea=stdin.readline().strip().split()
- for p in linea:
- mapa[i,j]=int(p)
- j+=1
- nl+=1
- if(j>columnas):
- j=1
- i+=1
- if columnas==1:
- mv=1e99
- indice=-1
- for i in mapa:
- if mapa[i] < mv:
- mv=mapa[i]
- indice=i[0]
- print(indice)
- print(mapa[indice,1])
- else:
- seem_carving(filas,columnas,mapa)
- linea=stdin.readline()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement