Submission #16587790


Source Code Expand

Copy
import networkx as nx

R, C = [int(x) for x in input().split()]
grid = [list(input()) for r in range(R)]


def pack(r, c):
    return r * C + c


graph = nx.Graph()
top_nodes = set()  # top half of the bipartite graph
for r in range(R):
    for c in range(C):
        if r + 1 < R and grid[r][c] == grid[r + 1][c] == ".":
            u, v = pack(r, c), pack(r + 1, c)
            graph.add_edge(u, v)
            if (r + c) % 2 == 0:
                top_nodes.add(v)
            else:
                top_nodes.add(u)
        if c + 1 < C and grid[r][c] == grid[r][c + 1] == ".":
            u, v = pack(r, c), pack(r, c + 1)
            graph.add_edge(u, v)
            if (r + c) % 2 == 0:
                top_nodes.add(v)
            else:
                top_nodes.add(u)


matching = nx.bipartite.maximum_matching(graph, top_nodes=top_nodes)

count = 0
for u, v in matching.items():
    if u > v:
        assert matching[v] == u
        r1, c1 = divmod(u, C)
        r2, c2 = divmod(v, C)
        if r1 == r2:
            if c1 > c2:
                c1, c2 = c2, c1
            grid[r1][c1], grid[r2][c2] = ">", "<"
        elif c1 == c2:
            if r1 > r2:
                r1, r2 = r2, r1
            grid[r1][c1] = "v"
            grid[r2][c2] = "^"
        count += 1

print(count)
for row in grid:
    print("".join(row))

Submission Info

Submission Time
Task D - Maxflow
User atf
Language Python (3.8.2)
Score 100
Code Size 1390 Byte
Status AC
Exec Time 632 ms
Memory 66496 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 19
Set Name Test Cases
Sample 00-sample-01.txt
All 00-sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 333 ms 52784 KB
01-01.txt AC 332 ms 52780 KB
01-02.txt AC 331 ms 53048 KB
01-03.txt AC 323 ms 53088 KB
01-04.txt AC 329 ms 53052 KB
01-05.txt AC 331 ms 53132 KB
01-06.txt AC 329 ms 53032 KB
01-07.txt AC 534 ms 62804 KB
01-08.txt AC 336 ms 53332 KB
01-09.txt AC 325 ms 53176 KB
01-10.txt AC 339 ms 53508 KB
01-11.txt AC 338 ms 53080 KB
01-12.txt AC 632 ms 66496 KB
01-13.txt AC 509 ms 61876 KB
01-14.txt AC 393 ms 58012 KB
01-15.txt AC 347 ms 54796 KB
01-16.txt AC 330 ms 53112 KB
01-17.txt AC 438 ms 58020 KB
01-18.txt AC 442 ms 58032 KB