Day 169-Q4 — 2026-10-04 | 行と列のレーザーで全部の的を消す（二部グラフの最小頂点被覆を König の定理で復元する）

📋 コピーimport sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    h, w, n = int(data[0]), int(data[1]), int(data[2])
    adj = [[] for _ in range(h + 1)]           # 行 r -> 点のある列
    for i in range(n):
        r = int(data[3 + 2 * i]); c = int(data[4 + 2 * i])
        adj[r].append(c)
    rows = [r for r in range(1, h + 1) if adj[r]]
    INF = 1 << 30
    match_r = [0] * (h + 1)                     # 行 -> 列（0 は未マッチ）
    match_c = [0] * (w + 1)                     # 列 -> 行
    dist = [0] * (h + 1)

    # Hopcroft–Karp: 最短の増加路だけを層ごとにまとめて流す
    while True:
        q = deque()
        for r in rows:
            if match_r[r] == 0:
                dist[r] = 0
                q.append(r)
            else:
                dist[r] = INF
        found = False
        while q:
            r = q.popleft()
            for c in adj[r]:
                r2 = match_c[c]
                if r2 == 0:
                    found = True
                elif dist[r2] == INF:
                    dist[r2] = dist[r] + 1
                    q.append(r2)
        if not found:
            break
        it = [0] * (h + 1)
        for s in rows:
            if match_r[s]:
                continue
            # 反復版 DFS で層を 1 つずつ下る増加路を探す
            stack = [s]
            while stack:
                r = stack[-1]
                advanced = False
                while it[r] < len(adj[r]):
                    c = adj[r][it[r]]
                    r2 = match_c[c]
                    if r2 == 0:
                        # 増加路が見つかった: スタック上の行を順に付け替える
                        for k in range(len(stack) - 1, -1, -1):
                            rr = stack[k]
                            cc = adj[rr][it[rr]]
                            match_r[rr] = cc
                            match_c[cc] = rr
                        stack = []
                        advanced = True
                        break
                    if dist[r2] == dist[r] + 1:
                        stack.append(r2)
                        advanced = True
                        break
                    it[r] += 1
                if not advanced:
                    dist[r] = INF            # この行からは増加路が無い
                    stack.pop()
                    if stack:
                        it[stack[-1]] += 1

    # König: 未マッチの行から交互路（行→非マッチ辺→列→マッチ辺→行）で届く集合 Z
    vis_r = [False] * (h + 1)
    vis_c = [False] * (w + 1)
    q = deque()
    for r in rows:
        if match_r[r] == 0:
            vis_r[r] = True
            q.append(r)
    while q:
        r = q.popleft()
        for c in adj[r]:
            if not vis_c[c]:
                vis_c[c] = True
                r2 = match_c[c]           # Z の列は必ずマッチ済み（でなければ増加路がある）
                if not vis_r[r2]:
                    vis_r[r2] = True
                    q.append(r2)
    # 最小頂点被覆 = (Z に入らない行) ∪ (Z に入った列)
    ans = [f"R {r}" for r in rows if not vis_r[r]] + [f"C {c}" for c in range(1, w + 1) if vis_c[c]]
    sys.stdout.write(str(len(ans)) + "\n" + "\n".join(ans) + "\n")


main()