Problem p02561 (python)

Fixed submission:
import networkx as nx

def main():
  N,M=map(int,input().split())
  S = [list(input()) for _ in range(N)]

  if N == M == 1:
    print(0)
    print(S[0][0])
    exit()

  index = lambda i,j: i*M+j

  G=nx.Graph()
  dx,dy=(1,0),(0,1)
  E = []
  n1,n2 = [],[]
  for i in range(N):
    for j in range(M):
      if S[i][j]=='#':continue
      if (i+j)%2:
        n1.append(index(i,j))
      else:
        n2.append(index(i,j))
      for k in range(2):
        v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
        if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
          continue
        if S[i+dx[k]][j+dy[k]] == '#': continue
        if (i+j) % 2:
          E.append((v2,v1))
        else:
          E.append((v1,v2))
     
  G.add_nodes_from(n1, bipartite=0)
  G.add_nodes_from(n2, bipartite=1)
  G.add_edges_from(E)
  u = [n for n in G.nodes if G.nodes[n]['bipartite'] == 0]
  match = nx.bipartite.maximum_matching(G, top_nodes=u)
  match = {v:match[v] for v in match.keys() if v < match[v]}
 
  for v in match.keys():
    i1,j1 = divmod(v,M)
    i2,j2 = divmod(match[v],M)
    if i1 > i2 or j1 > j2:
      (i1,j1),(i2,j2) = (i2,j2),(i1,j1)
    if i1 < i2:
      S[i1][j1] = 'v'
      S[i2][j2] = '^'
    else:
      S[i1][j1] = '>'
      S[i2][j2] = '<'

  print(len(match))
  for i in range(N):
    print(''.join(S[i]))
    
if __name__ == "__main__":
  main()

Buggy submission (verdict: Runtime Error):
import networkx as nx

def main():
  N,M=map(int,input().split())
  S = [list(input()) for _ in range(N)]

  if N == M == 1:
    print(0)
    print(S[0][0])
    exit()

  index = lambda i,j: i*M+j

  G=nx.Graph()
  dx,dy=(1,0),(0,1)
  E = []
  n1,n2 = [],[]
  for i in range(N):
    for j in range(M):
      if S[i][j]=='#':continue
      if (i+j)%2:
        n1.append(index(i,j))
      else:
        n2.append(index(i,j))
      for k in range(2):
        v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
        if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
          continue
        if S[i+dx[k]][j+dy[k]] == '#': continue
        if (i+j) % 2:
          E.append((v2,v1))
        else:
          E.append((v1,v2))
     
  G.add_nodes_from(n1, bipartite=0)
  G.add_nodes_from(n2, bipartite=1)
  G.add_edges_from(E)
  match = nx.bipartite.maximum_matching(G)
  match = {v:match[v] for v in match.keys() if v < match[v]}
 
  for v in match.keys():
    i1,j1 = divmod(v,M)
    i2,j2 = divmod(match[v],M)
    if i1 > i2 or j1 > j2:
      (i1,j1),(i2,j2) = (i2,j2),(i1,j1)
    if i1 < i2:
      S[i1][j1] = 'v'
      S[i2][j2] = '^'
    else:
      S[i1][j1] = '>'
      S[i2][j2] = '<'

  print(len(match))
  for i in range(N):
    print(''.join(S[i]))
    
if __name__ == "__main__":
  main()

Buggy submission (verdict: Runtime Error):
import networkx as nx

def main():
  N,M=map(int,input().split())
  S = [list(input()) for _ in range(N)]

  if N == M == 1:
    print(0)
    print(S[0][0])
    exit()

  index = lambda i,j: i*M+j

  G=nx.DiGraph()
  G.add_node('source')
  G.add_node('sink')
  dx,dy=(1,0),(0,1)
  E = []
  for i in range(N):
    for j in range(M):
      if S[i][j]=='#':continue
      if (i+j) %2:
        E.append((index(i,j),'sink'))
      else:
        E.append(('source',index(i,j))
      for k in range(2):
        v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
        if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
          continue
        if S[i+dx[k]][j+dy[k]] == '#': continue
        if (i+j) % 2:
          E.append((v2,v1))
        else:
          E.append((v1,v2))
     
  G.add_edges_from(E,capacity=1)
  flow_value, flow_dict = nx.maximum_flow(G, "source", "sink")

  for v1 in flow_dict.keys():
    if v1 in ('sink','source'):continue
    for v2 in flow_dict[v1].keys():
      if v2 in ('sink','source'):continue
      if flow_dict[v1][v2]:
        i1,j1 = divmod(v1,M)
        i2,j2 = divmod(v2,M)
        if i1 > i2 or j1 > j2:
          (i1,j1),(i2,j2) = (i2,j2),(i1,j1)
        if i1 < i2:
          S[i1][j1] = 'v'
          S[i2][j2] = '^'
        else:
          S[i1][j1] = '>'
          S[i2][j2] = '<'

  print(flow_value)
  for i in range(N):
    print(''.join(S[i]))
    
if __name__ == "__main__":
  main()

Buggy submission (verdict: Runtime Error):
import networkx as nx

def main():
  N,M=map(int,input().split())
  S = [list(input()) for _ in range(N)]

  if N == M == 1:
    print(0)
    print(S[0][0])
    exit()

  index = lambda i,j: i*M+j

  G=nx.DiGraph()
  G.add_node('source')
  G.add_node('sink')
  dx,dy=(1,0),(0,1)
  for i in range(N):
    for j in range(M):
      if S[i][j]=='#':continue
      if (i+j) %2:
        G.add_edge(index(i,j),'sink',capacity=1)
      else:
        G.add_edge('source',index(i,j),capacity=1)
      for k in range(2):
        v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
        if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
          continue
        if S[i+dx[k]][j+dy[k]] == '#': continue
        if (i+j) % 2:
          G.add_edge(v2,v1,capacity=1)
        else:
          G.add_edge(v1,v2,capacity=1)
         
  flow_value, flow_dict = nx.maximum_flow(G, "source", "sink")
  assert False

  for v1 in flow_dict.keys():
    if v1 in ('sink','source'):continue
    for v2 in flow_dict[v1]:
      if v2 in ('sink','source'):continue
      if flow_dict[v1][v2]:
        i1,j1 = divmod(v1,M)
        i2,j2 = divmod(v2,M)
        (i1,j1),(i2,j2) = sorted([(i1,j1),(i2,j2)])
        if i1 + 1 == i2:
          S[i1][j1] = 'v'
          S[i2][j2] = '^'
        else:
          S[i1][j1] = '>'
          S[i2][j2] = '<'

  print(flow_value)
  for i in range(N):
    print(''.join(S[i]))
    
if __name__ == "__main__":
  main()

Buggy submission (verdict: Runtime Error):
import networkx as nx

def main():
  N,M=map(int,input().split())
  S = [list(input()) for _ in range(N)]

  if N == M == 1:
    print(0)
    print(S[0][0])
    exit()

  index = lambda i,j: i*M+j

  G=nx.DiGraph()
  G.add_node('source')
  G.add_node('sink')
  dx,dy=(1,0),(0,1)
  for i in range(N):
    for j in range(M):
      if S[i][j]=='#':continue
      if (i+j) %2:
        G.add_edge(index(i,j),'sink',capacity=1)
      else:
        G.add_edge('source',index(i,j),capacity=1)
      for k in range(2):
        v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
        if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
          continue
        if S[i+dx[k]][j+dy[k]] == '#': continue
        if (i+j) % 2:
          G.add_edge(v2,v1,capacity=1)
        else:
          G.add_edge(v1,v2,capacity=1)
         
  print(0/0)
  flow_value, flow_dict = nx.maximum_flow(G, "source", "sink")

  for v1 in flow_dict.keys():
    if v1 in ('sink','source'):continue
    for v2 in flow_dict[v1]:
      if v2 in ('sink','source'):continue
      if flow_dict[v1][v2]:
        i1,j1 = divmod(v1,M)
        i2,j2 = divmod(v2,M)
        (i1,j1),(i2,j2) = sorted([(i1,j1),(i2,j2)])
        if i1 + 1 == i2:
          S[i1][j1] = 'v'
          S[i2][j2] = '^'
        else:
          S[i1][j1] = '>'
          S[i2][j2] = '<'

  print(flow_value)
  for i in range(N):
    print(''.join(S[i]))
    
if __name__ == "__main__":
  main()

Buggy submission (verdict: Runtime Error):
import networkx as nx

N,M=map(int,input().split())
S = [input() for _ in range(N)]

index = lambda i,j: i*M+j

G=nx.DiGraph()
dx,dy=(1,0),(0,1)
for i in range(N):
  for j in range(M):
    if S[i][j]=='#':continue
    if (i+j) %2:
      G.add_edge(index(i,j),'sink',capacity=1)
    else:
      G.add_edge('source',index(i,j),capacity=1)
    for k in range(2):
      v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
      if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
        continue
      if S[i+dx[k]][j+dy[k]] == '#': continue
      if (i+j) % 2:
        G.add_edge(v2,v1,capacity=1)
      else:
        G.add_edge(v1,v2,capacity=1)
        
flow_value, flow_dict = nx.maximum_flow(G, "source", "sink")

ans = [list(S[i]) for i in range(N)]
for v1 in flow_dict.keys():
  if v1 in ('sink','source'):continue
  for v2 in flow_dict[v1]:
    if v2 in ('sink','source'):continue
    if flow_dict[v1][v2]:
      i1,j1 = divmod(v1,M)
      i2,j2 = divmod(v2,M)
      (i1,j1),(i2,j2) = sorted([(i1,j1),(i2,j2)])
      if i1 + 1 == i2:
        ans[i1][j1] = 'v'
        ans[i2][j2] = '^'
      else:
        ans[i1][j1] = '>'
        ans[i2][j2] = '<'

print(flow_value)
for i in range(N):
  print(''.join(ans[i]))

Buggy submission (verdict: Runtime Error):
import networkx as nx

N,M=map(int,input().split())
S = [input() for _ in range(N)]

index = lambda i,j: i*M+j

G=nx.DiGraph()
dx,dy=(1,0),(0,1)
for i in range(N):
  for j in range(M):
    if S[i][j]=='#':continue
    if (i+j) %2:
      G.add_edge(index(i,j),'sink',capacity=1)
    else:
      G.add_edge('source',index(i,j),capacity=1)
    for k in range(2):
      v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
      if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
        continue
      if S[i+dx[k]][j+dy[k]] == '#': continue
      if (i+j) % 2:
        G.add_edge(v2,v1,capacity=1)
      else:
        G.add_edge(v1,v2,capacity=1)
        
flow_value, flow_dict = nx.maximum_flow(G, "source", "sink")

ans = [list(S[i]) for i in range(N)]
for v1 in flow_dict.keys():
  if v1 in ('sink','source'):continue
  for v2 in flow_dict[v1]:
    if v2 in ('sink','source'):continue
    if flow_dict[v1][v2]:
      i1,j1 = divmod(v1,N)
      i2,j2 = divmod(v2,N)
      (i1,j1),(i2,j2) = sorted([(i1,j1),(i2,j2)])
      if i1 + 1 == i2:
        ans[i1][j1] = 'v'
        ans[i2][j2] = '^'
      else:
        ans[i1][j1] = '>'
        ans[i2][j2] = '<'
        
for i in range(N):
  print(''.join(ans[i]))