Submission #20563184

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import maximum_flow
c2i = dict(zip("BW?", [0, 1, -1]))
dij = [(-1, 0), (0, 1), (1, 0), (0, -1)]
INF = 10**6
def main() -> None:
    N = int(input())
    if N == 1:
        print(0)
        return
    board = [[c2i[x] for x in input()] for _ in range(N)]
    # reverse (i+j)%2==0
    for i in range(N):
        for j in range(N):
            if (i+j) % 2 == 0 and board[i][j] != -1:
                board[i][j] ^= 1
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import maximum_flow


c2i = dict(zip("BW?", [0, 1, -1]))
dij = [(-1, 0), (0, 1), (1, 0), (0, -1)]

INF = 10**6


def main() -> None:
    N = int(input())
    if N == 1:
        print(0)
        return
    board = [[c2i[x] for x in input()] for _ in range(N)]
    # reverse (i+j)%2==0
    for i in range(N):
        for j in range(N):
            if (i+j) % 2 == 0 and board[i][j] != -1:
                board[i][j] ^= 1
    edges = []
    source, sink = N*N, N*N + 1
    w, fr, to = [], [], []
    for i in range(N):
        for j in range(N):
            v = i * N + j
            if board[i][j] == 0:
                w.append(INF)
                fr.append(source)
                to.append(v)
            elif board[i][j] == 1:
                w.append(INF)
                fr.append(v)
                to.append(sink)
            for di, dj in dij:
                ni, nj = i+di, j+dj
                if ni < 0 or N <= ni or nj < 0 or N <= nj:
                    continue
                nv = ni * N + nj
                w.append(1)
                fr.append(v)
                to.append(nv)
    graph = csr_matrix((w, (fr, to)), shape=(N*N+2, N*N+2))
    print(2 * N * (N - 1) - maximum_flow(graph, source, sink).flow_value)


if __name__ == '__main__':
    main()

Submission Info

Judge Result