Problem p03979 (python)

Fixed submission:
import numpy as np

H, W = map(int, raw_input().split())
S_list = list()
for i in range(H):
    S_list.append(raw_input())

# large_const
large_const = 100000

X_mat = np.zeros((H, W), dtype='int')
# S_mat_extend = np.zeros((H+2, W+2), dtype='int')

# input
for h in range(H):
    for w in range(W):
        if S_list[h][w] == 'X':
            X_mat[h, w] += 1

# make graph
G = dict()
def add_node(s, Graph=G):
    Graph[s] = {'edges':dict()}
    
def add_edge(s, t, weight=1, Graph=G):
    Graph[s]['edges'][t] = weight

def max_flow_dinic(s, t, Graph=G):
    G_ = Graph
    max_flow = 0
    while True:
        # create level Graph(reverse)
        # initialize
        for v in G_.keys():
            G_[v]['dist'] = -1
        # dst
        G_[t]['dist'] = 0
        # bfs 
        que_bfs = [t]
        dmax = large_const
        while len(que_bfs) > 0:
            v = que_bfs.pop(0)
            if G_[v]['dist'] >= dmax:
                # if too far, pass
                pass
            else:
                # else update dist
                for d in G_[v]['edges'].keys():    
                    if G_[d]['edges'][v] > 0:
                        if d == s:
                            # src reached
                            # update
                            dmax = min(dmax, G_[v]['dist'] + 1)
                            G_[d]['dist'] = dmax
                        elif G_[d]['dist'] == -1:
                            # update
                            G_[d]['dist'] = G_[v]['dist'] + 1
                            que_bfs.append(d)
                        elif G_[d]['dist'] > G_[v]['dist'] + 1:
                            # update (may not happen)
                            G_[d]['dist'] = G_[v]['dist'] + 1
                            que_bfs.append(d)
                        else:
                            pass
        
        if G_[s]['dist'] == -1:
            break
        else:
            # find blocking flow with respect to current dist
            # dfs
            que_dfs = [[s]]
            while len(que_dfs) > 0:
                path = que_dfs.pop()
                # check if valid
                if len(path) == 1:
                    pass
                elif G_[path[0]]['edges'][path[1]] == 0:
                    continue
                v = path[-1]
                # add
                for d in G_[v]['edges'].keys():
                    if G_[v]['edges'][d] > 0 and G_[d]['dist'] == G_[v]['dist'] - 1:
                        if d == t:
                            # if reached
                            path.append(d)
                            # add flow and update graph with residual
                            # eps = min([G_[path[i]]['edges'][path[i+1]] for i in range(len(path) - 1)])
                            eps = 1
                            max_flow += eps
                            # imax = len(path)-2
                            for i in range(len(path) - 1):
                                G_[path[i]]['edges'][path[i+1]] -= eps
                                G_[path[i+1]]['edges'][path[i]] += eps
                                # if G_[path[i]]['edges'][path[i+1]] == 0:
                                #     imax = min(imax, i)
                        else:
                            # append to que
                            que_dfs.append(path + [d])
            
    
    return max_flow


# src:sheeps
# dst:outer
add_node('src')
add_node('dst')

# grid
# nodes
for i in range(H):
    for j in range(W):
        if X_mat[i, j] == 1:
            pass
        else:
            add_node(str([i, j]) + '-src')
            add_node(str([i, j]) + '-dst')

# edges
for i in range(H):
    for j in range(W):
        if X_mat[i, j] == 1:
            pass
        else:
            add_edge(str([i, j]) + '-dst', str([i, j]) + '-src', 1)
            add_edge(str([i, j]) + '-src', str([i, j]) + '-dst', 0)
            for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                k = i + d[0]
                l = j + d[1]
                if k in [-1, H] or l in [-1, W]:
                    add_edge('src', str([i, j]) + '-dst', 1)
                    add_edge(str([i, j]) + '-dst', 'src', 0)
                elif X_mat[k, l] == 1:
                    add_edge(str([i, j]) + '-src', 'dst', 1)
                    add_edge('dst', str([i, j]) + '-src', 0)                    
                else:
                    add_edge(str([i, j]) + '-src', str([k, l]) + '-dst', 1)
                    add_edge(str([k, l]) + '-dst', str([i, j]) + '-src', 0)

res = 0
# find -1
if X_mat[0,:].sum() + X_mat[H-1,:].sum() + X_mat[:,0].sum() + X_mat[:,W-1].sum() > 0:
    res = -1
else:
    res = max_flow_dinic('src', 'dst')


print res

Buggy submission (verdict: Runtime Error):

H, W = map(int, raw_input().split())
S_list = list()
for i in range(H):
    S_list.append(raw_input())

# large_const
large_const = 100000

# X_mat = np.zeros((H, W), dtype='int')
X_mat = [[0]*W]*H

# input
for h in range(H):
    for w in range(W):
        if S_list[h][w] == 'X':
            X_mat[h, w] += 1

# make graph
G = dict()
def add_node(s, Graph=G):
    Graph[s] = {'edges':dict()}
    
def add_edge(s, t, weight=1, Graph=G):
    Graph[s]['edges'][t] = weight

def max_flow_dinic(s, t, Graph=G):
    G_ = Graph
    max_flow = 0
    while True:
        # create level Graph(reverse)
        # initialize
        for v in G_.keys():
            G_[v]['dist'] = -1
        # dst
        G_[t]['dist'] = 0
        # bfs 
        que_bfs = [t]
        dmax = large_const
        while len(que_bfs) > 0:
            v = que_bfs.pop(0)
            if G_[v]['dist'] >= dmax:
                # if too far, pass
                pass
            else:
                # else update dist
                for d in G_[v]['edges'].keys():    
                    if G_[d]['edges'][v] > 0:
                        if d == s:
                            # src reached
                            # update
                            dmax = min(dmax, G_[v]['dist'] + 1)
                            G_[d]['dist'] = dmax
                        elif G_[d]['dist'] == -1:
                            # update
                            G_[d]['dist'] = G_[v]['dist'] + 1
                            que_bfs.append(d)
                        elif G_[d]['dist'] > G_[v]['dist'] + 1:
                            # update (may not happen)
                            G_[d]['dist'] = G_[v]['dist'] + 1
                            que_bfs.append(d)
                        else:
                            pass
        
        if G_[s]['dist'] == -1:
            break
        else:
            # find blocking flow with respect to current dist
            # dfs
            que_dfs = [[s]]
            while len(que_dfs) > 0:
                path = que_dfs.pop()
                # check if valid
                if len(path) == 1:
                    pass
                elif G_[path[0]]['edges'][path[1]] == 0:
                    continue
                v = path[-1]
                # add
                for d in G_[v]['edges'].keys():
                    if G_[v]['edges'][d] > 0 and G_[d]['dist'] == G_[v]['dist'] - 1:
                        if d == t:
                            # if reached
                            path.append(d)
                            # add flow and update graph with residual
                            # eps = min([G_[path[i]]['edges'][path[i+1]] for i in range(len(path) - 1)])
                            eps = 1
                            max_flow += eps
                            # imax = len(path)-2
                            for i in range(len(path) - 1):
                                G_[path[i]]['edges'][path[i+1]] -= eps
                                G_[path[i+1]]['edges'][path[i]] += eps
                                # if G_[path[i]]['edges'][path[i+1]] == 0:
                                #     imax = min(imax, i)
                        else:
                            # append to que
                            que_dfs.append(path + [d])
            
    
    return max_flow


# src:sheeps
# dst:outer
add_node('src')
add_node('dst')

# grid
# nodes
for i in range(H):
    for j in range(W):
        if X_mat[i, j] == 1:
            pass
        else:
            add_node(str([i, j]) + '-src')
            add_node(str([i, j]) + '-dst')

# edges
for i in range(H):
    for j in range(W):
        if X_mat[i, j] == 1:
            pass
        else:
            add_edge(str([i, j]) + '-dst', str([i, j]) + '-src', 1)
            add_edge(str([i, j]) + '-src', str([i, j]) + '-dst', 0)
            for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                k = i + d[0]
                l = j + d[1]
                if k in [-1, H] or l in [-1, W]:
                    add_edge('src', str([i, j]) + '-dst', 1)
                    add_edge(str([i, j]) + '-dst', 'src', 0)
                elif X_mat[k, l] == 1:
                    add_edge(str([i, j]) + '-src', 'dst', 1)
                    add_edge('dst', str([i, j]) + '-src', 0)                    
                else:
                    add_edge(str([i, j]) + '-src', str([k, l]) + '-dst', 1)
                    add_edge(str([k, l]) + '-dst', str([i, j]) + '-src', 0)

res = 0
# find -1
if X_mat[0,:].sum() + X_mat[H-1,:].sum() + X_mat[:,0].sum() + X_mat[:,W-1].sum() > 0:
    res = -1
else:
    res = max_flow_dinic('src', 'dst')


print res

Buggy submission (verdict: Runtime Error):
import numpy as np

H, W = map(int, raw_input().split())
S_list = list()
for i in range(H):
    S_list.append(raw_input())

# large_const
large_const = 100000

X_mat = np.zeros((H, W), dtype='int')
S_mat_extend = np.zeros((H+2, W+2), dtype='int')

# input
for h in range(H):
    for w in range(W):
        if S_list[h][w] == 'X':
            X_mat[h, w] += 1

# make graph
G = dict()
def add_node(s, Graph=G):
    Graph[s] = {'edges':dict()}
    
def add_edge(s, t, weight=1, Graph=G):
    Graph[s]['edges'][t] = weight

def max_flow_dinic(s, t, Graph=G):
    G_ = Graph
    max_flow = 0
    while True:
        # create level Graph(reverse)
        # initialize
        for v in G_.keys():
            G_[v]['dist'] = -1
        # dst
        G_[t]['dist'] = 0
        # bfs 
        que_bfs = [t]
        dmax = large_const
        while len(que_bfs) > 0:
            v = que_bfs.pop(0)
            if G_[v]['dist'] >= dmax:
                # if too far, pass
                pass
            else:
                # else update dist
                for d in G_[v]['edges'].keys():    
                    if G_[d]['edges'][v] > 0:
                        if d == s:
                            # src reached
                            # update
                            dmax = min(dmax, G_[v]['dist'] + 1)
                            G_[d]['dist'] = dmax
                        elif G_[d]['dist'] == -1:
                            # update
                            G_[d]['dist'] = G_[v]['dist'] + 1
                            que_bfs.append(d)
                        elif G_[d]['dist'] > G_[v]['dist'] + 1:
                            # update (may not happen)
                            G_[d]['dist'] = G_[v]['dist'] + 1
                            que_bfs.append(d)
                        else:
                            pass
        
        if G_[s]['dist'] == -1:
            break
        else:
            # find blocking flow with respect to current dist
            # dfs
            que_dfs = [[s]]
            while len(que_dfs) > 0:
                path = que_dfs.pop()
                # check if valid
                if len(path) == 1:
                    pass
                elif G_[path[0]]['edges'][path[1]] == 0:
                    continue
                v = path[-1]
                # add
                for d in G_[v]['edges'].keys():
                    if G_[v]['edges'][d] > 0 and G_[d]['dist'] == G_[v]['dist'] - 1:
                        if d == t:
                            # if reached
                            path.append(d)
                            # add flow and update graph with residual
                            # eps = min([G_[path[i]]['edges'][path[i+1]] for i in range(len(path) - 1)])
                            eps = 1
                            max_flow += eps
                            # imax = len(path)-2
                            for i in range(len(path) - 1):
                                G_[path[i]]['edges'][path[i+1]] -= eps
                                G_[path[i+1]]['edges'][path[i]] += eps
                                # if G_[path[i]]['edges'][path[i+1]] == 0:
                                #     imax = min(imax, i)
                        else:
                            # append to que
                            que_dfs.append(path + [d])
            
    
    return max_flow


# src:sheeps
# dst:outer
add_node('src')
add_node('dst')

# grid
# nodes
for i in range(H):
    for j in range(W):
        if X_mat[i, j] == 1:
            pass
        else:
            add_node(str([i, j]) + '-src')
            add_node(str([i, j]) + '-dst')

# edges
for i in range(H):
    for j in range(W):
        if X_mat[i, j] == 1:
            pass
        else:
            add_edge(str([i, j]) + '-dst', str([i, j]) + '-src', 1)
            add_edge(str([i, j]) + '-src', str([i, j]) + '-dst', 0)
            for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                k = i + d[0]
                l = j + d[1]
                if k in [-1, H] or l in [-1, W]:
                    add_edge('src', str([i, j]) + '-dst', 1)
                    add_edge(str([i, j]) + '-dst', 'src', 0)
                elif X_mat[k, l] == 1:
                    add_edge(str([i, j]) + '-src', 'dst', 1)
                    add_edge('dst', str([i, j]) + '-src', 0)                    
                else:
                    add_edge(str([i, j]) + '-src', str([k, l]) + '-dst', 1)
                    add_edge(str([k, l]) + '-dst', str([i, j]) + '-src', 0)

res = 0
# find -1
if X_mat[0,:].sum() + X_mat[H-1,:].sum() + X_mat[:,0].sum() + X_mat[:,W-1].sum() > 0:
    res = -1
else:
    res = max_flow_dinic('src', 'dst')


print res

Buggy submission (verdict: Runtime Error):


X_mat = np.zeros((H, W), dtype='int')
S_mat_extend = np.zeros((H+2, W+2), dtype='int')
# input
for h in range(H):
    for w in range(W):
        if S_list[h][w] == 'X':
            X_mat[h, w] += 1

# make graph
G = dict()
def add_node(s, Graph=G):
    Graph[s] = {'edges':dict()}
    
def add_edge(s, t, weight=1, Graph=G):
    Graph[s]['edges'][t] = weight

def shortest_path(s, t, Graph=G):
    G_ = Graph.copy()
    # initialize
    for v in G_.keys():
        G_[v]['dist'] = float('inf')
        G_[v]['path'] = ''
    G_[s]['dist'] = 0
    # bfs
    ques = [s]
    while len(ques) > 0:
        v = ques.pop(0)
        for d in G_[v]['edges'].keys():
            if G_[v]['edges'][d] > 0 and G_[v]['dist'] + G_[v]['edges'][d] < G_[d]['dist']:
                # update
                G_[d]['dist'] = G_[v]['dist'] + G_[v]['edges'][d]
                G_[d]['path'] = v
                ques.append(d)
    path = []
    if G_[t]['path'] != '':
        path.append(t)
        while True:
            v = path[-1]
            path.append(G_[v]['path'])
            if G_[v]['path'] == s:
                break
    path.reverse()
    return path

# reverse path    
def minus_flow(path, Graph=G):
    if len(path) > 0:
        # flow
        flow = min([Graph[path[i]]['edges'][path[i+1]] for i in range(len(path)-1)])
        for i in range(len(path)-1):
            Graph[path[i]]['edges'][path[i+1]] -= flow
            # minus
            if path[i] not in Graph[path[i+1]]['edges'].keys():
                add_edge(path[i+1], path[i], weight=0, Graph=Graph)
            Graph[path[i+1]]['edges'][path[i]] += flow
        return flow
    else:
        return 0

# src:sheeps
# dst:outer
add_node('src')
add_node('dst')

# grid
for i in range(H):
    for j in range(W):
        add_node(str([i, j]) + '-src')
        add_node(str([i, j]) + '-dst')
        add_edge(str([i, j]) + '-dst', str([i, j]) + '-src')
        if X_mat[i, j] == 1:
            add_edge('src', str([i, j]) + '-dst', 100000)
            add_edge(str([i, j]) + '-dst', str([i, j]) + '-src', 100000)
        if i > 0:
            add_edge(str([i, j]) + '-src', str([i-1, j]) + '-dst')
        if i < H-1:
            add_edge(str([i, j]) + '-src', str([i+1, j]) + '-dst')
        if j > 0:
            add_edge(str([i, j]) + '-src', str([i, j-1]) + '-dst')
        if j < W-1:
            add_edge(str([i, j]) + '-src', str([i, j+1]) + '-dst')
        if i == 0 or j == 0 or i == H-1 or j == W-1:
            add_edge(str([i, j]) + '-src', 'dst')

res = 0
while True:
    p = shortest_path('src', 'dst')
    res_add = minus_flow(p)
    if res_add == 0:
        break
    else:
        res += res_add

print res