D - Maxflow https://atcoder.jp/contests/practice2/tasks/practice2_d

practice2_d.py

from atcoder.maxflow import MFGraph


def index(i, j):
    return i * M + j


N, M = map(int, input().split())
S = [list(input()) for _ in range(N)]
g = MFGraph(N * M + 2)
source, sink = N * M, N * M + 1
dir = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(N):
    for j in range(M):
        if (i + j) % 2 == 0:  # 黒色：偶数
            for dx, dy in dir:
                i2 = i + dx
                j2 = j + dy
                if i2 < 0 or i2 >= N or j2 < 0 or j2 >= M:
                    continue
                # どちらも空マスならば、ドミノを置けるので、辺を結ぶ
                if S[i][j] == "." and S[i2][j2] == ".":
                    g.add_edge(index(i, j), index(i2, j2), 1)
        # source から黒色マスへの辺を結ぶ
        if (i + j) % 2 == 0 and S[i][j] == ".":
            g.add_edge(source, index(i, j), 1)
        # 白色マスからsinkへの辺を結ぶ
        if (i + j) % 2 == 1 and S[i][j] == ".":
            g.add_edge(index(i, j), sink, 1)

ans = g.flow(source, sink)
for e in g.edges():
    # 辺eが超頂点に接続するものや、フロー値が0であるものはスキップ
    if e.src == source or e.dst == sink or e.flow == 0:
        continue
    # 辺eの両端点に対応するマス
    ifrom, jfrom = divmod(e.src, M)
    ito, jto = divmod(e.dst, M)
    # ドミノを置く
    if ifrom == ito:
        # ドミノを横に配置する場合
        if jfrom > jto:
            jfrom, jto = jto, jfrom
        S[ifrom][jfrom] = ">"
        S[ito][jto] = "<"
    else:
        # ドミノを縦に配置する場合
        if ifrom > ito:
            ifrom, ito = ito, ifrom
        S[ifrom][jfrom] = "v"
        S[ito][jto] = "^"

# 出力
print(ans)
for i in range(N):
    print("".join(S[i]))