#import sys
from time import perf_counter

def minDistance():
    global dist
    global sptSetList
    min = 99999 #sys.maxsize
    for v in sptSetList:
        if dist[v] < min:
            min = dist[v]
            min_index = v
    return min_index


with open('input15') as f:
    lines = f.read().splitlines()
t1=perf_counter()
maxx=len(lines[0])
maxy=len(lines)
fold=5

V = (maxy*fold)*(maxx*fold)
graph = [[] for node in range(V)]
dist = [99999]*V #[sys.maxsize] * V

print("Populate graph")
for y in range(maxy*fold):
    for x in range(maxx*fold):
        if x>0:
            risk=(int(lines[y%maxy][(x-1)%maxx])+(x-1)//maxx+y//maxy)
            risk=(risk-1)%9+1
            graph[y*maxx*fold+x].append([y*maxx*fold+(x-1),risk])
        if y>0:
            risk=(int(lines[(y-1)%maxy][x%maxx])+x//maxx+(y-1)//maxy)
            risk=(risk-1)%9+1
            graph[y*maxx*fold+x].append([(y-1)*maxx*fold+x,risk])
        if x<(maxx*fold-1):
            risk=(int(lines[y%maxy][(x+1)%maxx])+(x+1)//maxx+y//maxy)
            risk=(risk-1)%9+1
            graph[y*maxx*fold+x].append([y*maxx*fold+(x+1),risk])
        if y<(maxy*fold-1):
            risk=(int(lines[(y+1)%maxy][x%maxx])+x//maxx+(y+1)//maxy)
            risk=(risk-1)%9+1
            graph[y*maxx*fold+x].append([(y+1)*maxx*fold+x,risk])
print("Compute solution")

dist[0] = 0
sptSet = [False] * V
sptSetList=[]
for v in range(V):
    sptSetList.append(v)

for cout in range(V):
    if cout%1000==0:
        print(cout//1000,'/',V//1000)
    u = minDistance()

    sptSet[u] = True
    sptSetList.remove(u)

    for nd in graph[u]:
        if sptSet[nd[0]] == False and dist[nd[0]] > dist[u] + nd[1]:
            dist[nd[0]] = dist[u] + nd[1]

print("Distance of vertex from source")
print(V-1, "t", dist[V-1])
t2=perf_counter()
print("Elapsed time: %.3f ms" % round(1e3*(t2-t1),3))