パナソニックグループ プログラミングコンテスト2025（AtCoder Beginner Contest 427）E,F問題メモ

from collections import deque


def solve(h, w, field):
    ti, tj = 0, 0
    for i in range(h):
        try:
            j = field[i].index('T')
        except:
            continue
        ti = i
        tj = j
        break

    def blows_out_all(u, d, l, r):
        i1 = min(h, max(0, d - ti))
        i2 = min(h, max(0, h - (ti - u)))
        j1 = min(w, max(0, r - tj))
        j2 = min(w, max(0, w - (tj - l)))
        cnt = 0
        for i in range(i1, i2):
            cnt += field[i][j1:j2].count('#')
        # print(f'{u=} {d=} {l=} {r=} {i1=} {i2=} {j1=} {j2=} {cnt=}')
        return cnt == 0

    def can_move(u, d, l, r, i, j, direction):
        if direction == 0:
            i -= 1
            if i < d - ti:
                return True
        elif direction == 1:
            i += 1
            if i >= h - (ti - u):
                return True
        elif direction == 2:
            j -= 1
            if j < r - tj:
                return True
        else:
            j += 1
            if j >= w - (tj - l):
                return True
        if i < 0 or h <= i or j < 0 or w <= j:
            return True
        return field[i][j] != '#'

    dp = {(ti, ti, tj, tj, ti, tj): 0}
    q = deque([(ti, ti, tj, tj, ti, tj)])
    while q:
        key = q.popleft()
        u, d, l, r, i, j = key
        cost = dp[key]
        if blows_out_all(u, d, l, r):
            return cost
        for dd, (di, dj) in enumerate(((-1, 0), (1, 0), (0, -1), (0, 1))):
            if not can_move(u, d, l, r, i, j, dd):
                continue
            ni = i + di
            nj = j + dj
            nu = min(u, ni)
            nd = max(d, ni)
            nl = min(l, nj)
            nr = max(r, nj)
            nk = (nu, nd, nl, nr, ni, nj)
            if nk in dp:
                continue
            dp[nk] = cost + 1
            q.append(nk)

    return -1


h, w = map(int, input().split())
field = [input() for _ in range(h)]
ans = solve(h, w, field)
print(ans)

from collections import defaultdict


def solve(n, m, aaa):
    def half(si, ti, step):
        dp0 = defaultdict(int, {0: 1})
        dp1 = defaultdict(int)
        for i in range(si, ti, step):
            a = aaa[i]
            ndp = defaultdict(int)
            for b, c in dp0.items():
                ndp[(a + b) % m] += c
            for b, c in dp1.items():
                dp0[b] += c
            dp1 = ndp
        return dp0, dp1

    if n == 1:
        if aaa[0] % m == 0:
            return 2
        return 1

    h = n // 2
    f0, f1 = half(0, h, 1)
    b0, b1 = half(n - 1, h - 1, -1)
    ans = 0
    for fb, fc in f0.items():
        bb = -fb % m
        if bb in b0:
            ans += b0[bb] * fc
        if bb in b1:
            ans += b1[bb] * fc
    for fb, fc in f1.items():
        bb = -fb % m
        if bb in b0:
            ans += b0[bb] * fc
    return ans


n, m = map(int, input().split())
aaa = list(map(int, input().split()))
ans = solve(n, m, aaa)
print(ans)