SHARE
TWEET

Untitled

a guest Feb 15th, 2016 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import sys
  2. from sys import stdin
  3.  
  4. ##Es el seem_carving de practicas pero MODIFICANDO LA RECONSTRUCCION DEL CAMINO
  5. ##Recontruir el camino en este problema es una locura.
  6.  
  7. def seem_carving(filas,columnas,mapa):
  8.     infty=1e99
  9.     mat = [[infty for x in range(columnas+1)] for y in range(filas+1)]
  10.     backpointers=[[ [] for x in range(columnas+1)] for y in range(filas+1)]
  11.  
  12.  
  13.     for x in range(1,filas+1):
  14.         mat[x][0] = infty
  15.         mat[x][1] = mapa[x,1]
  16.         backpointers[x][1]=[x]
  17.     ##Programacion dinamica
  18.     for j in range(2,columnas+1):
  19.        
  20.         for i in range(1,filas+1):
  21.             iup=i-1
  22.             if iup<=0:
  23.                 iup=filas
  24.             idown=i+1
  25.             if idown>filas:
  26.                 idown=1
  27.             aux=min(mat[iup][j-1], mat[i][j-1],mat[idown][j-1]) + mapa[i,j]
  28.             mat[i][j]=aux
  29.             prueba=[iup,i,idown]
  30.             posibles=[]
  31.             for q in prueba:
  32.                 if  mat[i][j]- mapa[i,j]==mat[q][j-1]:
  33.                     posibles.append(backpointers[q][j-1]+[i])
  34.             posibles.sort()
  35.             backpointers[i][j]=posibles[0]
  36.  
  37.  
  38.     #for i in range(1,filas+1):
  39.     #   s=""
  40.     #   for j in range(1,columnas+1):
  41.     #       s+=str(mapa[i,j])+" "
  42.     #   print(s)
  43.     #for i in mat:
  44.     #   print(i)
  45.     #for i in backpointers:
  46.     #   print(i)
  47.  
  48.     ##Minval y min_point
  49.     min_val = 1e99
  50.     min_point =-1
  51.     for i in range(1,filas+1):
  52.         if mat[i][columnas] < min_val:
  53.             min_val=mat[i][columnas]
  54.             min_point=i
  55.  
  56.     coste=mat[min_point][columnas]
  57.  
  58.  
  59.     ##PATH
  60.     todos_paths=[]
  61.     for i in range(1,filas+1):
  62.         if mat[i][columnas] ==min_val:
  63.             todos_paths.append(backpointers[i][j])
  64.  
  65.  
  66.     todos_paths.sort()
  67.     path=todos_paths[0]
  68.  
  69.     print(" ".join([str(x) for x in path]))
  70.     print(coste)
  71.  
  72.  
  73. linea=stdin.readline()
  74. linea.strip()
  75.  
  76. while(linea!=''):
  77.     linea=linea.split()
  78.     filas=int(linea[0])
  79.     columnas=int(linea[1])
  80.     nn=filas*columnas
  81.     mapa={}
  82.     nl=0
  83.     i=1
  84.     j=1
  85.     while(nl<nn):
  86.         linea=stdin.readline().strip().split()
  87.         for p in linea:
  88.             mapa[i,j]=int(p)
  89.             j+=1
  90.             nl+=1
  91.             if(j>columnas):
  92.                 j=1
  93.                 i+=1
  94.  
  95.     if columnas==1:
  96.         mv=1e99
  97.         indice=-1
  98.         for i in mapa:
  99.             if mapa[i] < mv:
  100.                 mv=mapa[i]
  101.                 indice=i[0]
  102.         print(indice)
  103.         print(mapa[indice,1])
  104.  
  105.     else:
  106.         seem_carving(filas,columnas,mapa)
  107.     linea=stdin.readline()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top