#1182176 (Python3) No.3738 Right Hamiltonian

• 問題: No.3738 Right Hamiltonian
• ユーザー: 👑 kencho
• 提出日時: 2026-09-03 04:46:59
• 言語: Python3 (3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 6,900 bytes
• コンパイル時間: 60 ms
• コンパイル使用メモリ: 16,256 KB
• 実行使用メモリ: 154,496 KB
• 最終ジャッジ日時: 2026-09-19 13:02:43
• 合計ジャッジ時間: 25,582 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

サブタスク	配点	結果
部分点	80 %	AC * 38
満点	20 %	AC * 56 TLE * 2 -- * 2
合計	4 * 80% = 320 点

ソースコード

import sys
from bisect import bisect_left, bisect_right

data = sys.stdin.buffer
H, W = map(int, data.readline().split())
grid = [data.readline().strip() for _ in range(H)]
DR, DC = (-1, 0, 1, 0), (0, 1, 0, -1)
total, U, D, L, R = 0, H, -1, W, -1
for r, row in enumerate(grid):
    count = row.count(b".")
    if count:
        total += count
        U, D = min(U, r), r
        L, R = min(L, row.find(b".")), max(R, row.rfind(b"."))

def num(r, c): return r * W + c
def direction(x, y):
    xr, xc, yr, yc = x // W, x % W, y // W, y % W
    return next(d for d in range(4) if yr - xr == DR[d] and yc - xc == DC[d])
def border():
    return ([num(U, c) for c in range(L, R)] + [num(r, R) for r in range(U, D)] +
            [num(D, c) for c in range(R, L, -1)] + [num(r, L) for r in range(D, U, -1)])
def inside(z, r, c): return z[0] <= r <= z[1] and z[2] <= c <= z[3]

def rect_count(z):
    u, d, l, r = z
    if u > d or l > r: return 0
    if l == il and r == ir:
        return row_sum[d + 1] - row_sum[u]
    return col_sum[r + 1] - col_sum[l]

def ray_distance(r, c, d):
    walls = col_walls[c] if d % 2 == 0 else row_walls[r]
    x = r if d % 2 == 0 else c
    if d in (0, 3):
        return x - walls[bisect_left(walls, x) - 1]
    return walls[bisect_right(walls, x)] - x

def spiral(z, start, d, turn):
    r, c, got, segments, first = start // W, start % W, 0, [], True
    while True:
        def distance():
            x, y = r + DR[d], c + DC[d]
            if not inside(z, x, y) or grid[x][y] == 35: return 0
            n = x - z[0] + 1 if d == 0 else z[3] - y + 1 if d == 1 else z[1] - x + 1 if d == 2 else y - z[2] + 1
            n = min(n, ray_distance(x, y, d))
            if len(segments) >= 3:
                qr, qc, qd, qn = segments[-3]
                er, ec = qr + DR[qd] * qn, qc + DC[qd] * qn
                if d % 2 and min(qr, er) <= r <= max(qr, er):
                    gap = (qc - c) * DC[d]
                    if gap == 0: return -1
                    if gap > 0: n = min(n, gap - 1)
                if d % 2 == 0 and min(qc, ec) <= c <= max(qc, ec):
                    gap = (qr - r) * DR[d]
                    if gap == 0: return -1
                    if gap > 0: n = min(n, gap - 1)
            return n
        length = distance()
        if first and length == 0:
            d = (d + turn) % 4
            length = distance()
        if length < 0: return None
        if length == 0: break
        if len(segments) >= 2 and length >= segments[-2][3]: return None
        segments.append((r, c, d, length))
        r += DR[d] * length; c += DC[d] * length; got += length
        first = False; d = (d + turn) % 4
    return segments if got == rect_count(z) else None

used = bytearray(H * W)
def trace(start, d, turn, tag):
    r, c, segments, count = start // W, start % W, [], 0
    while True:
        sr, sc, length = r, c, 0
        while True:
            x, y = r + DR[d], c + DC[d]
            if not (0 <= x < H and 0 <= y < W) or grid[x][y] == 35 or used[num(x, y)] == tag: break
            r, c, length, count = x, y, length + 1, count + 1
            used[num(r, c)] = tag
        if length: segments.append((sr, sc, d, length))
        d = (d + turn) % 4
        x, y = r + DR[d], c + DC[d]
        if not (0 <= x < H and 0 <= y < W) or grid[x][y] == 35 or used[num(x, y)] == tag: break
    return segments, count

def add(run, d, length):
    if not length: return
    if run and run[-1][0] == d: run[-1] = (d, run[-1][1] + length)
    else: run.append((d, length))
def reverse_arm(run, segments):
    for _, _, d, length in reversed(segments): add(run, d ^ 2, length)
def forward_arm(run, segments):
    for _, _, d, length in segments: add(run, d, length)
def emit(start, run):
    moves, commands = 0, []
    for i, (d, length) in enumerate(run):
        if i and d != (run[i - 1][0] + 1) % 4: return False
        moves += length; commands.append(("R" if i else "F") + "F" * (length - 1))
    if moves != total - 1: return False
    print(start // W + 1, start % W + 1, "URDL"[run[0][0] if run else 0])
    print(moves); print("".join(commands))
    return True

def partial(arc, order):
    tag = order + 1
    for cell in arc: used[cell] = tag
    fd, ld = direction(arc[0], arc[1]), direction(arc[-2], arc[-1])
    if order == 0:
        x, cx = trace(arc[0], fd ^ 2, -1, tag); y, cy = trace(arc[-1], ld, 1, tag)
    else:
        y, cy = trace(arc[-1], ld, 1, tag); x, cx = trace(arc[0], fd ^ 2, -1, tag)
    if len(arc) + cx + cy != total: return False
    run = []; reverse_arm(run, x)
    for i in range(1, len(arc)): add(run, direction(arc[i - 1], arc[i]), 1)
    forward_arm(run, y)
    start = arc[0] if not x else num(x[-1][0] + DR[x[-1][2]] * x[-1][3], x[-1][1] + DC[x[-1][2]] * x[-1][3])
    return emit(start, run)

if U == D or L == R:
    length = R - L + 1 if U == D else D - U + 1
    if length != total: print(-1)
    else: emit(num(U, L), [] if length == 1 else [(1 if U == D else 2, length - 1)])
    raise SystemExit

p = border(); n = len(p)
is_floor = [grid[x // W][x % W] == 46 for x in p]
if not all(is_floor):
    starts = [i for i in range(n) if is_floor[i] and not is_floor[(i - 1) % n]]
    if len(starts) != 1:
        print(-1); raise SystemExit
    arc, i = [], starts[0]
    while is_floor[i]: arc.append(p[i]); i = (i + 1) % n
    if len(arc) >= 2 and (partial(arc, 0) or partial(arc, 1)): raise SystemExit
    print(-1); raise SystemExit

iu, id_, il, ir = U + 1, D - 1, L + 1, R - 1
row_walls = []
col_walls = [[-1] for _ in range(W)]
for r, row in enumerate(grid):
    walls = [-1]
    for c, value in enumerate(row):
        if value == 35:
            walls.append(c)
            col_walls[c].append(r)
    walls.append(W)
    row_walls.append(walls)
for walls in col_walls:
    walls.append(H)
row_sum = [0]
for r in range(H):
    row_sum.append(row_sum[-1] + grid[r][il:ir + 1].count(b"."))
col_sum = [0]
for c in range(W):
    col_sum.append(col_sum[-1] + sum(grid[r][c] == 46 for r in range(iu, id_ + 1)))
for k in range(n):
    A, B = p[(k + 1) % n], p[k]
    ar, ac, br, bc = A // W, A % W, B // W, B % W
    if ar == br:
        q = max(ac, bc); left, right = (iu, id_, il, q - 1), (iu, id_, q, ir)
        xz, yz = (right, left) if ac >= q else (left, right)
    else:
        q = max(ar, br); upper, lower = (iu, q - 1, il, ir), (q, id_, il, ir)
        xz, yz = (lower, upper) if ar >= q else (upper, lower)
    fd, ld = direction(A, p[(k + 2) % n]), direction(p[(k - 1) % n], B)
    x, y = spiral(xz, A, fd ^ 2, -1), spiral(yz, B, ld, 1)
    if x is None or y is None: continue
    run = []; reverse_arm(run, x)
    for i in range(1, n): add(run, direction(p[(k + i) % n], p[(k + i + 1) % n]), 1)
    forward_arm(run, y)
    start = A if not x else num(x[-1][0] + DR[x[-1][2]] * x[-1][3], x[-1][1] + DC[x[-1][2]] * x[-1][3])
    if emit(start, run): raise SystemExit
print(-1)