18
https://adventofcode.com/2024/day/18
Prob1
python
import sys
import queue
w = int(sys.argv[1])
t = int(sys.argv[2])
tab = [[0]*w for i in range(w)]
for i, line in enumerate(sys.stdin):
if i >= t:
break
x, y = map(int, line.strip().split(','))
tab[y][x] = 1
for l in tab:
print(l)
inf = 1000000000
dp = [[inf]*w for i in range(w)]
que = queue.Queue()
que.put((0, (0, 0)))
while not que.empty():
dist, (x, y) = que.get()
if dist >= dp[y][x]:
continue
dp[y][x] = dist
for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= w or ny < 0 or ny >= w:
continue
if tab[ny][nx] == 1:
continue
que.put((dist + 1, (nx, ny)))
print(dp[w-1][w-1])Prob2
不是最佳解，應該要用 Disjoint-Set
python
import sys
import queue
w = int(sys.argv[1])
block_list = []
for i, line in enumerate(sys.stdin):
x, y = map(int, line.strip().split(','))
block_list.append((x, y))
def check(tab):
inf = 1000000000
dp = [[inf]*w for i in range(w)]
que = queue.Queue()
que.put((0, (0, 0)))
while not que.empty():
dist, (x, y) = que.get()
if dist >= dp[y][x]:
continue
dp[y][x] = dist
for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= w or ny < 0 or ny >= w:
continue
if tab[ny][nx] == 1:
continue
que.put((dist + 1, (nx, ny)))
return dp[w-1][w-1] != inf
tab = [[0]*w for i in range(w)]
for block_pt in block_list:
x, y = block_pt
tab[y][x] = 1
if not check(tab):
print('%d,%d' % (x, y))
break