提出 #76576195

---

ソースコード 拡げる

from atcoder.maxflow import MFGraph

N, M = map(int, input().split())
S = [list(input().strip()) for _ in range(N)]
s = N * M
t = s + 1
G = MFGraph(t + 1)

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

def dec(num):
    i = num // M
    j = num % M
    return i, j

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

for i in range(N):
    for j in range(M):
        if S[i][j] == '#':
            continue
        if (i + j) % 2 == 0:
            G.add_edge(s, enc(i, j), 1)
            for d in range(4):
                ni, nj = i + dy[d], j + dx[d]
                if not(0 <= ni < N and 0 <= nj < M) or S[ni][nj] == '#':
                    continue
                G.add_edge(enc(i, j), enc(ni, nj), 1)
        else:
            G.add_edge(enc(i, j), t, 1)

print(G.flow(s, t))
for e in G.edges():
    if e.src == s or e.dst == t or e.flow == 0:
        continue
    ai, aj = dec(e.src)
    bi, bj = dec(e.dst)
    if ai + 1 == bi:
        S[ai][aj] = 'v'
        S[bi][bj] = '^'
    elif bi + 1 == ai:
        S[ai][aj] = '^'
        S[bi][bj] = 'v'
    elif aj + 1 == bj:
        S[ai][aj] = '>'
        S[bi][bj] = '<'
    else:
        S[ai][aj] = '<'
        S[bi][bj] = '>'

for s in S:
    print(''.join(s))

提出情報

ジャッジ結果