Day 172-Q2 — 2026-10-08 | 端点を指定したハミルトン路の数（括弧 2 種＋「端点につながる線」の 3 記号のプラグ DP）

📋 コピーimport sys

MOD = 998244353


def match(st, j, w):
    # 位置 j の括弧（'('=1 / ')'=2）と対になる括弧の位置を返す
    d = 0
    if (st >> 2 * j) & 3 == 1:
        for i in range(j, w + 1):
            c = (st >> 2 * i) & 3
            if c == 1:
                d += 1
            elif c == 2:
                d -= 1
                if d == 0:
                    return i
    else:
        for i in range(j, -1, -1):
            c = (st >> 2 * i) & 3
            if c == 2:
                d += 1
            elif c == 1:
                d -= 1
                if d == 0:
                    return i
    raise AssertionError


def setp(st, i, c):
    return st & ~(3 << 2 * i) | (c << 2 * i)


def main(mod=MOD):
    data = sys.stdin.read().split()
    h, w = int(data[0]), int(data[1])
    g = data[2:2 + h]
    if w > h:                                   # 狭い方を幅にする（状態数は幅で決まる）
        g = [''.join(g[i][j] for i in range(h)) for j in range(w)]
        h, w = w, h
    dp = {0: 1}
    for i in range(h):
        for j in range(w):
            c = g[i][j]
            down_ok = i + 1 < h and g[i + 1][j] != '#'
            right_ok = j + 1 < w and g[i][j + 1] != '#'
            ndp = {}

            def add(s, v):
                ndp[s] = (ndp.get(s, 0) + v) % mod if mod else ndp.get(s, 0) + v

            for st, v in dp.items():
                L = (st >> 2 * j) & 3                # 左から入る線（位置 j）
                U = (st >> 2 * (j + 1)) & 3          # 上から入る線（位置 j+1）
                base = setp(setp(st, j, 0), j + 1, 0)
                if c == '#':
                    if L == 0 and U == 0:
                        add(st, v)
                    continue
                if c in 'ST':                        # 端点: 次数 1
                    if L and U:
                        continue
                    if L == 0 and U == 0:            # ここから線を 1 本出す（記号 3 = 端点につながる線）
                        if down_ok:
                            add(setp(base, j, 3), v)
                        if right_ok:
                            add(setp(base, j + 1, 3), v)
                        continue
                    x, pos = (L, j) if L else (U, j + 1)
                    if x == 3:                       # 反対の端点からの線が届いた = 路が完成
                        add(base, v)
                    else:                            # 括弧の線を端点で止めると、相手の括弧が端点につながる線になる
                        add(setp(base, match(st, pos, w), 3), v)
                    continue
                # 通常のマス: 次数 2
                if L == 0 and U == 0:
                    if down_ok and right_ok:
                        add(setp(setp(base, j, 1), j + 1, 2), v)
                elif L == 0 or U == 0:
                    x = L | U
                    if down_ok:
                        add(setp(base, j, x), v)
                    if right_ok:
                        add(setp(base, j + 1, x), v)
                else:
                    if L == 1 and U == 2:            # 閉路ができる: ハミルトン路では禁止
                        continue
                    if L == 2 and U == 1:            # ')(' はそのままつながる
                        add(base, v)
                    elif L == 1 and U == 1:          # '((' : 上の線の相手 ')' が '(' になる
                        add(setp(base, match(st, j + 1, w), 1), v)
                    elif L == 2 and U == 2:          # '))' : 左の線の相手 '(' が ')' になる
                        add(setp(base, match(st, j, w), 2), v)
                    elif L == 3 and U == 3:          # S 側と T 側の線がつながる = 路が完成
                        add(base, v)
                    else:                            # 端点の線と括弧: 括弧の相手が端点の線になる
                        b, pos = (U, j + 1) if L == 3 else (L, j)
                        add(setp(base, match(st, pos, w), 3), v)
            dp = ndp
        dp = {st << 2: v for st, v in dp.items() if (st >> 2 * w) & 3 == 0}   # 行末: 右端の線は 0 のはず
    return dp.get(0, 0)


if __name__ == "__main__":
    print(main())