Day 173-Q1 — 2026-10-09 | 端点を指定しないハミルトン路の数（3 記号のプラグ DP に「使った端点の数 k」を足す）

📋 コピー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 solve(h, w, g, mod=MOD):
    if w > h:                                   # 狭い方を幅にする
        g = [''.join(g[i][j] for i in range(h)) for j in range(w)]
        h, w = w, h
    if sum(row.count('.') for row in g) == 1:   # 1 マスだけなら長さ 0 の路が 1 本
        return 1
    dp = {0: 1}                                 # キー = 境界の状態 * 4 + 使った端点の数 k
    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, k, v):
                key = s << 2 | k
                ndp[key] = (ndp.get(key, 0) + v) % mod

            for key, v in dp.items():
                st, k = key >> 2, key & 3
                L = (st >> 2 * j) & 3                # 左から入る線
                U = (st >> 2 * (j + 1)) & 3          # 上から入る線
                base = setp(setp(st, j, 0), j + 1, 0)
                if c == '#':
                    if L == 0 and U == 0:
                        add(st, k, v)
                    continue
                # (a) このマスを端点にする（次数 1）。端点は全体で 2 個まで
                if k < 2 and not (L and U):
                    if L == 0 and U == 0:
                        if down_ok:
                            add(setp(base, j, 3), k + 1, v)
                        if right_ok:
                            add(setp(base, j + 1, 3), k + 1, v)
                    else:
                        x, pos = (L, j) if L else (U, j + 1)
                        if x == 3:                   # もう一方の端点からの線が届いた = 路が完成
                            add(base, k + 1, v)
                        else:                        # 括弧を止めると相手が「端点につながる線」になる
                            add(setp(base, match(st, pos, w), 3), k + 1, v)
                # (b) 通常の通過マス（次数 2）
                if L == 0 and U == 0:
                    if down_ok and right_ok:
                        add(setp(setp(base, j, 1), j + 1, 2), k, v)
                elif L == 0 or U == 0:
                    x = L | U
                    if down_ok:
                        add(setp(base, j, x), k, v)
                    if right_ok:
                        add(setp(base, j + 1, x), k, v)
                else:
                    if L == 1 and U == 2:            # 閉路になる: 禁止
                        continue
                    if L == 2 and U == 1:
                        add(base, k, v)
                    elif L == 1 and U == 1:
                        add(setp(base, match(st, j + 1, w), 1), k, v)
                    elif L == 2 and U == 2:
                        add(setp(base, match(st, j, w), 2), k, v)
                    elif L == 3 and U == 3:          # 両端点の線がつながる = 路が完成
                        add(base, k, v)
                    else:                            # 端点の線と括弧: 括弧の相手が端点の線になる
                        pos = j + 1 if L == 3 else j
                        add(setp(base, match(st, pos, w), 3), k, v)
            dp = ndp
        # 行末: 右端の線は 0 のはず。記号列を 1 つずらし、k の 2 ビットはそのまま
        dp = {(key >> 2) << 4 | (key & 3): v for key, v in dp.items() if (key >> 2 * w + 2) & 3 == 0}
    return dp.get(2, 0)                         # 記号列が全部 0 で k = 2


def main():
    data = sys.stdin.read().split()
    h, w = int(data[0]), int(data[1])
    print(solve(h, w, data[2:2 + h]))


if __name__ == "__main__":
    main()