12

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

Prob1

題目

給定一個上色地圖，計算所有聯通塊的週長x面積的和。

範例

Input

AAA
AAC
BBA

Output

AAA
AA.

面積=5 週長=9

C

面積=1 週長=4

BB

面積=2 週長=6

A

面積=1 週長=4

65

解法

先把連通塊上不同顏色，然後就可以迭代每個點：

1. 這個顏色有這塊面積。
2. 假如向某個方向是不同色的，就代表該連通塊有這個方向的邊。

import sys

from typing import Dict, List


def recolor(mat: List[str]) -> List[str]:
    row_max = len(mat)
    col_max = len(mat[0])

    ret = [['']*col_max for r in range(row_max)]

    def color(i, j, c, target):
        if i < 0 or j < 0 or i >= row_max or j >= col_max:
            return

        if ret[i][j]:
            return

        if mat[i][j] != target:
            return

        ret[i][j] = c
        color(i - 1, j, c, target)
        color(i + 1, j, c, target)
        color(i, j - 1, c, target)
        color(i, j + 1, c, target)

    idx = 0
    for r in range(row_max):
        for c in range(col_max):
            if ret[r][c]:
                continue
            color(r, c, str(idx), mat[r][c])
            idx += 1

    return ret


mat = []
for line in sys.stdin:
    mat.append(line.strip())

mat = recolor(mat)

area: Dict[str, int] = {}
row_max = len(mat)
col_max = len(mat[0])
for row in mat:
    for c in row:
        area.setdefault(c, 0)
        area[c] += 1


def get(r: int, c: int) -> str:
    if r < 0 or c < 0 or r >= row_max or c >= col_max:
        return '.'
    return mat[r][c]


mult: Dict[str, int] = {}
for i in range(row_max):
    for j in range(col_max):
        for (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if get(i + di, j + dj) != mat[i][j]:
                mult.setdefault(mat[i][j], 0)
                mult[mat[i][j]] += 1

print(area, mult)

ans = 0
for c in area:
    print(c, area[c], mult[c])
    ans += area[c]*mult[c]

print(ans)

Prob2

題目

給定一個上色地圖，計算所有聯通塊的邊數x面積的和。

範例

Input

AAA
AAC
BBA

Output

AAA
AA.

面積=5 邊數=6

C

面積=1 邊數=4

BB

面積=2 週長=4

A

面積=1 週長=4

46

解法

先把連通塊上不同顏色，然後就可以迭代每個點：

1. 這個顏色有這塊面積。
2. 假如向某個方向是不同色的，就代表該連通塊有這個方向的邊。

import sys

from typing import Dict, List


def recolor(mat: List[str]) -> List[List[str]]:
    row_max = len(mat)
    col_max = len(mat[0])

    ret = [['']*col_max for r in range(row_max)]

    def color(i, j, c, target):
        if i < 0 or j < 0 or i >= row_max or j >= col_max:
            return

        if ret[i][j]:
            return

        if mat[i][j] != target:
            return

        ret[i][j] = c
        color(i - 1, j, c, target)
        color(i + 1, j, c, target)
        color(i, j - 1, c, target)
        color(i, j + 1, c, target)

    idx = 0
    for r in range(row_max):
        for c in range(col_max):
            if ret[r][c]:
                continue
            color(r, c, str(idx), mat[r][c])
            idx += 1

    return ret


def cal_seg(seg: List[int]) -> int:
    cnt = 1
    for i in range(len(seg) - 1):
        if seg[i] != seg[i+1] - 1:
            cnt += 1
    return cnt


def main():
    mat = []
    for line in sys.stdin:
        mat.append(line.strip())

    mat = recolor(mat)
    print(mat)

    def get(r: int, c: int) -> str:
        if r < 0 or c < 0 or r >= row_max or c >= col_max:
            return '.'
        return mat[r][c]

    area: Dict[str, int] = {}
    row_max = len(mat)
    col_max = len(mat[0])
    for row in mat:
        for c in row:
            area.setdefault(c, 0)
            area[c] += 1

    edge_table: Dict[str, Dict[str, List[int]]] = {}
    for i in range(row_max):
        for j in range(col_max):
            for dir, (di, dj) in enumerate([(-1, 0), (1, 0), (0, -1), (0, 1)]):
                if get(i + di, j + dj) == mat[i][j]:
                    continue

                if dir == 0 or dir == 1:
                    edge_name = f'{dir}_{i}'
                    edge_idx = j
                else:
                    edge_name = f'{dir}_{j}'
                    edge_idx = i

                edge_table.setdefault(mat[i][j], {}).setdefault(
                    edge_name, []).append(edge_idx)

    ans = 0
    for c in area:
        edge_cnt = 0
        print(edge_table[c])
        for edge_name, segs in edge_table[c].items():
            edge_cnt += cal_seg(segs)
        ans += area[c]*edge_cnt
        print(c, area[c], edge_cnt)

    print(ans)


if __name__ == '__main__':
    main()

Changelog

Last edited 6 days ago

View full history

f880830-Update