74 lines
1.5 KiB
Python
74 lines
1.5 KiB
Python
#!/usr/bin/env python
|
|
|
|
density = []
|
|
distance = []
|
|
import copy
|
|
|
|
def full_map(density):
|
|
# append columns
|
|
for row in density:
|
|
o = copy.copy(row)
|
|
for count in range(4):
|
|
for x in o:
|
|
t = (x+count+1)
|
|
if t > 9:
|
|
t += 1
|
|
row.append(t%10)
|
|
|
|
# append rows
|
|
rows = len(density)
|
|
for count in range(4):
|
|
for r in range(rows):
|
|
t = []
|
|
for v in density[r]:
|
|
v = v+count+1
|
|
if v > 9:
|
|
v += 1
|
|
t.append(v%10)
|
|
density.append(t)
|
|
|
|
def shortes_path(density, distance):
|
|
queue = []
|
|
queue.append((0,0))
|
|
|
|
#import pdb; pdb.set_trace()
|
|
while(len(queue)):
|
|
pos = queue.pop(0)
|
|
v = distance[pos[1]][pos[0]]
|
|
|
|
for move in ((0,1), (0,-1), (1,0), (-1,0)):
|
|
move_x = move[0] + pos[0]
|
|
move_y = move[1] + pos[1]
|
|
|
|
if (move_x) < 0:
|
|
continue
|
|
if (move_y) < 0:
|
|
continue
|
|
if (move_y) >= len(density):
|
|
continue
|
|
if (move_x) >= len(density[move_y]):
|
|
continue
|
|
|
|
if distance[move_y][move_x] is None:
|
|
distance[move_y][move_x] = v + density[move_y][move_x]
|
|
queue.append((move_x, move_y))
|
|
continue
|
|
|
|
if density[move_y][move_x] + v < distance[move_y][move_x]:
|
|
distance[move_y][move_x] = v + density[move_y][move_x]
|
|
queue.append((move_x, move_y))
|
|
continue
|
|
|
|
with open("input01.txt","r") as f:
|
|
for line in f:
|
|
density.append([int(i) for i in line.strip()])
|
|
#distance.append([None]*len(line.strip()))
|
|
|
|
full_map(density)
|
|
for r in density:
|
|
distance.append([None]*len(r))
|
|
distance[0][0] = density[0][0]
|
|
|
|
shortes_path(density,distance)
|
|
print(distance[-1][-1]-distance[0][0])
|