Submission #16918766


Source Code Expand

Copy
import sys
import networkx as nx
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W = map(int, readline().split())
S = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W].astype('U1')

INF = 1 << 32

total_o = (S == 'o').sum()
G = nx.DiGraph()
sink = 'sink'
G.add_node(sink, demand=total_o)
for i in range(H):
    for j in range(W):
        if S[i, j] == '#':
            continue
        if S[i, j] == 'o':
            G.add_node((i, j), demand=-1)
            G.add_edge((i, j), sink, capacity=1, weight=0)
        elif S[i, j] == '.':
            G.add_node((i, j), demand=0)
            G.add_edge((i, j), sink, capacity=1, weight=0)
        if i + 1 < H and S[i + 1, j] != '#':
            G.add_edge((i, j), (i + 1, j), capacity=INF, weight=-1)
        if j + 1 < W and S[i, j + 1] != '#':
            G.add_edge((i, j), (i, j + 1), capacity=INF, weight=-1)

mcfc = nx.min_cost_flow_cost(G)
ans = -mcfc
print(ans)

Submission Info

Submission Time
Task C - Moving Pieces
User maspy
Language Python (3.8.2)
Score 600
Code Size 1031 Byte
Status
Exec Time 930 ms
Memory 60600 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
× 2
× 44
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt
All 00-sample-01.txt, 00-sample-02.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, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt
Case Name Status Exec Time Memory
00-sample-01.txt 361 ms 53248 KB
00-sample-02.txt 363 ms 53304 KB
01-01.txt 350 ms 53244 KB
01-02.txt 392 ms 53732 KB
01-03.txt 364 ms 53264 KB
01-04.txt 422 ms 55528 KB
01-05.txt 538 ms 57672 KB
01-06.txt 382 ms 53736 KB
01-07.txt 720 ms 58640 KB
01-08.txt 729 ms 58804 KB
01-09.txt 759 ms 58788 KB
01-10.txt 687 ms 58660 KB
01-11.txt 744 ms 58868 KB
01-12.txt 930 ms 60600 KB
01-13.txt 816 ms 59636 KB
01-14.txt 626 ms 58112 KB
01-15.txt 471 ms 57260 KB
01-16.txt 455 ms 56272 KB
01-17.txt 704 ms 57740 KB
01-18.txt 617 ms 57780 KB
01-19.txt 641 ms 57348 KB
01-20.txt 521 ms 57268 KB
01-21.txt 478 ms 56560 KB
01-22.txt 460 ms 56876 KB
01-23.txt 449 ms 56248 KB
01-24.txt 475 ms 56044 KB
01-25.txt 419 ms 55324 KB
01-26.txt 391 ms 55112 KB
01-27.txt 393 ms 55416 KB
01-28.txt 485 ms 55500 KB
01-29.txt 500 ms 55596 KB
01-30.txt 465 ms 55528 KB
01-31.txt 503 ms 55512 KB
01-32.txt 504 ms 55524 KB
01-33.txt 457 ms 55252 KB
01-34.txt 431 ms 55672 KB
01-35.txt 431 ms 55064 KB
01-36.txt 412 ms 55180 KB
01-37.txt 420 ms 55016 KB
01-38.txt 414 ms 55080 KB
01-39.txt 397 ms 55024 KB
01-40.txt 396 ms 54848 KB
01-41.txt 402 ms 54604 KB
01-42.txt 394 ms 54488 KB