94 lines
1.9 KiB
Python
94 lines
1.9 KiB
Python
from queue import Queue
|
|
|
|
with open("12.txt") as f:
|
|
data = f.read()
|
|
|
|
ex_data = """Sabqponm
|
|
abcryxxl
|
|
accszExk
|
|
acctuvwj
|
|
abdefghi"""
|
|
|
|
def parse_data(data):
|
|
arr = dict()
|
|
|
|
for y, line in enumerate(data.splitlines()):
|
|
line = line.strip()
|
|
for x, c in enumerate(line):
|
|
if c == "S": start = (x, y); arr[x, y] = "a"
|
|
elif c == "E": end = (x, y); arr[x, y] = "z"
|
|
else: arr[x, y] = c
|
|
|
|
return arr, start, end
|
|
|
|
def solve1(data):
|
|
arr, start, end = parse_data(data)
|
|
|
|
q = Queue()
|
|
q.put((0, start))
|
|
|
|
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
|
|
v = dict()
|
|
|
|
while not q.empty():
|
|
# print(q.queue)
|
|
steps, (x, y) = q.get()
|
|
if (x, y) == end:
|
|
print(steps)
|
|
break
|
|
if (x, y) in v:
|
|
continue
|
|
v[x, y] = steps
|
|
height = arr[x, y]
|
|
|
|
for (dx, dy) in dirs:
|
|
neighbor = (x + dx, y + dy)
|
|
if neighbor not in arr: continue
|
|
if neighbor in v: continue
|
|
nheight = arr[neighbor]
|
|
if ord(nheight) - ord(height) <= 1:
|
|
q.put((steps + 1, neighbor))
|
|
|
|
# input()
|
|
|
|
def solve2(data):
|
|
arr, _, end = parse_data(data)
|
|
|
|
starts = set()
|
|
for coord, c in arr.items():
|
|
if c == "a": starts.add(coord)
|
|
|
|
min_dist = len(arr)
|
|
for start in starts:
|
|
q = Queue()
|
|
q.put((0, start))
|
|
|
|
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
|
|
v = dict()
|
|
|
|
while not q.empty():
|
|
# print(q.queue)
|
|
steps, (x, y) = q.get()
|
|
if (x, y) == end:
|
|
min_dist = min(min_dist, steps)
|
|
break
|
|
if (x, y) in v:
|
|
continue
|
|
v[x, y] = steps
|
|
height = arr[x, y]
|
|
|
|
for (dx, dy) in dirs:
|
|
neighbor = (x + dx, y + dy)
|
|
if neighbor not in arr: continue
|
|
if neighbor in v: continue
|
|
nheight = arr[neighbor]
|
|
if ord(nheight) - ord(height) <= 1:
|
|
q.put((steps + 1, neighbor))
|
|
print(min_dist)
|
|
|
|
solve1(ex_data)
|
|
solve1(data)
|
|
|
|
solve2(ex_data)
|
|
solve2(data)
|