06
https://adventofcode.com/2024/day/6
Prob1
題目
給一張地圖，裡面有主角和障礙物，主角一開始向上走，只要碰到障礙物，就會右轉，然後繼續向前走。問：主角在離開地圖前經過幾個不一樣的方？
範例
Input
..#..
....#
...#.
..^..Output
把實際經過的地方打 x 就會得到：
..#..
xxxx#
..x#.
..x..所以答案是 6
6解法
直接模擬。
python
import sys
x_max = 0
y_max = 0
stone = set()
ch_dir = 0
ch_p = (0, 0)
dirs = [(0, -1), (1, 0), (0, 1), (-1, 0)]
for line in sys.stdin:
line = line.strip()
x_max = len(line)
y_max += 1
for x, c in enumerate(line):
p = (x + 1, y_max)
if c == '#':
stone.add(p)
elif c == '^':
ch_p = p
vis = set()
vis.add(ch_p)
while True:
dx, dy = dirs[ch_dir]
cx, cy = ch_p
nx = cx + dx
ny = cy + dy
if nx <= 0 or nx > x_max or ny <= 0 or ny > y_max:
break
if (nx, ny) in stone:
ch_dir = (ch_dir + 1) % 4
continue
ch_p = (nx, ny)
vis.add(ch_p)
print(len(vis))Prob2
題目
給一張地圖，裡面有主角和障礙物，主角一開始向上走，只要碰到障礙物，就會右轉，然後繼續向前走。
在地圖上增加一個石頭，可能會讓主角陷入迴圈，問有多少個點符合這條件？(排除直接在主角位置上增加石頭。)
Input
..#..
....#
...#.
..^..Output
把符合條件的地方打 x 就會得到：
..#..
.x..#
...#.
.....所以答案是 1
1解法
直接確認假如每個點追加一顆石頭的情況。
在檢查迴圈時，把『紀錄經過的點』變成『紀錄經過的點和當時方向』，這樣只要相同的『位置和方向』被重複經過，就可以判定有迴圈。
python
import sys
x_max = 0
y_max = 0
stone = set()
origin = (0, 0)
dirs = [(0, -1), (1, 0), (0, 1), (-1, 0)]
for line in sys.stdin:
line = line.strip()
x_max = len(line)
y_max += 1
for x, c in enumerate(line):
p = (x + 1, y_max)
if c == '#':
stone.add(p)
elif c == '^':
origin = p
cnt = 0
for stone_x in range(1, x_max + 1):
for stone_y in range(1, y_max + 1):
new_stone = (stone_x, stone_y)
if new_stone in stone:
continue
if new_stone == origin:
continue
ch_p = origin
ch_dir = 0
stone.add(new_stone)
vis = set()
vis.add((ch_p, ch_dir))
loop = False
while True:
dx, dy = dirs[ch_dir]
cx, cy = ch_p
nx = cx + dx
ny = cy + dy
if nx <= 0 or nx > x_max or ny <= 0 or ny > y_max:
break
if (nx, ny) in stone:
ch_dir = (ch_dir + 1) % 4
continue
ch_p = (nx, ny)
if (ch_p, ch_dir) in vis:
loop = True
break
vis.add((ch_p, ch_dir))
if loop:
print(new_stone)
cnt += 1
stone.remove(new_stone)
print(cnt)