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)
if (r + c) % 2 == 0:
else:
if c + 1 < C and grid[r][c] == grid[r][c + 1] == ".":
u, v = pack(r, c), pack(r, c + 1)
if (r + c) % 2 == 0:
else:

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 2020-09-09 10:14:32+0900 D - Maxflow atf Python (3.8.2) 100 1390 Byte AC 632 ms 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