Imgcity

Appearance

Imgcity✍️ Online Judge 題解AdventOfCode202410

10 ​

https://adventofcode.com/2024/day/10

Prob1 ​

題目 ​

給一個0-9 的高度地圖，問有幾個 9 可以從 0 走到(路徑經過的高度必須剛好按照順序 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)。

範例 ​

Input ​

0123456789
9876543210

Output ​

2

Code ​

python
import sys

from typing import Dict, List, Tuple, Set

mat = []

for line in sys.stdin:
    mat.append(list(map(int, line.strip())))

x_max = len(mat)
y_max = len(mat[0])


h_map: Dict[int, List[Tuple[int, int]]] = {}

for h in range(0, 10):
    h_map[h] = []

for i in range(x_max):
    for j in range(y_max):
        h_map[mat[i][j]].append((i, j))

tab: Dict[Tuple[int, int], Set[Tuple[int, int]]] = {}
for (x, y) in h_map[9]:
    tab[(x, y)] = {(x, y)}

for h in range(8, -1, -1):
    tab2: Dict[Tuple[int, int], int] = {}
    for (x, y) in h_map[h]:
        tab2[(x, y)] = tab.get((x + 1, y), set()) | \
                       tab.get((x - 1, y), set()) | \
                       tab.get((x, y + 1), set()) | \
                       tab.get((x, y - 1), set())
    tab = tab2

ans = 0
for pt, set9 in tab.items():
    ans += len(set9)

print(ans)

Prob2 ​

題目 ​

給一個 0-9 的高度地圖，問有多少條路徑(路徑必須剛好按照順序 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)。

Input ​

0123456789
9876543210

Output ​

4

解法 ​

DP

python
import sys

from typing import Dict, List, Tuple, Set

mat = []

for line in sys.stdin:
    mat.append(list(map(int, line.strip())))

x_max = len(mat)
y_max = len(mat[0])


h_map: Dict[int, List[Tuple[int, int]]] = {}

for h in range(0, 10):
    h_map[h] = []

for i in range(x_max):
    for j in range(y_max):
        h_map[mat[i][j]].append((i, j))

tab: Dict[Tuple[int, int], int] = {}
for (x, y) in h_map[9]:
    tab[(x, y)] = 1

for h in range(8, -1, -1):
    tab2: Dict[Tuple[int, int], int] = {}
    for (x, y) in h_map[h]:
        tab2[(x, y)] = tab.get((x + 1, y), 0) + \
                       tab.get((x - 1, y), 0) + \
                       tab.get((x, y + 1), 0) + \
                       tab.get((x, y - 1), 0)
    tab = tab2

ans = 0
for pt, cnt in tab.items():
    ans += cnt

print(ans)

Changelog

Just observe 👀