04

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

Prob1

題目

給一個字元方陣，找出橫的、直的、45度斜的 XMAS 的出現次數。

範例

Input

XMAS
MXXA
AXXM
SAMX

Output

4

解法

直接迭代每個點出發的 XMAS。時間複雜度 $O(NM)$

import sys

mat = []

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


mi = len(mat)
mj = len(mat[0])

def get_idx(x, y):
    if x < 0 or x >= mi or y < 0 or y >= mj:
        return '.'
    return mat[x][y]


cnt = 0

for i in range(mi):
    for j in range(mj):
        if mat[i][j] != 'X':
            continue

        # XMAS
        dt = [(-1, 1), (-1, 0), (-1, -1), (0, 1),
              (0, -1), (1, 1), (1, 0), (1, -1)]
        for di, dj in dt:
            w = get_idx(i + di, j + dj) + \
                get_idx(i + 2*di, j + 2*dj) + \
                get_idx(i + 3*di, j + 3*dj)
            if w == "MAS":
                cnt += 1

print(cnt)

Prob2

題目

找出所有形成 X 形狀的 MAS。

M.S
.A.
M.S

M.M
.A.
S.S

S.M
.A.
S.M

S.S
.A.
M.M

解法

迭代所有 A 的點，時間複雜度 $O(NM)$

import sys

mat = []

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

mi = len(mat)
mj = len(mat[0])

cnt = 0

for i in range(1, mi-1):
    for j in range(1, mj-1):
        if mat[i][j] != 'A':
            continue

        w = mat[i-1][j-1] + mat[i-1][j+1] + mat[i+1][j+1] + mat[i+1][j-1]
        if w in ['MMSS', 'MSSM', 'SSMM', 'SMMS']:
            cnt += 1

print(cnt)

Changelog

Last edited about 1 month ago

View full history

fba0b10-Update