Problem p03263 (python)

Fixed submission:
h, w = map(int, input().split())

a = [list(map(lambda x: int(x) % 2, input().split())) for _ in range(h)]

road = []
for i in range(h):
    for j in list(range(w))[::(i % 2) * -2 + 1]:
        road.append((i + 1, j + 1))

answer = []
for f, t in zip(road[:-1], road[1:]):
    if a[f[0] - 1][f[1] - 1] % 2:
        answer.append(f + t)
        a[t[0] - 1][t[1] - 1] += 1

print(len(answer))
for ans in answer:
    print(*ans)

Buggy submission (verdict: Runtime Error):
import copy
h, w = map(int, input().split())

a = [list(map(lambda x: int(x) % 2, input().split())) for _ in range(h)]
# for v in a:
#     print(*v)

directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visited = copy.deepcopy(a)
number = [[i * w + j for j in range(w)] for i in range(h)]
def bfs(x, y):
    graph = [[] for _ in range(h * w)]
    que = [(x, y)]
    visited[y][x] = 0
    while que:
        x, y = que.pop(0)
        n = number[y][x]

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < w and 0 <= ny < h and visited[ny][nx] == 1:
                que.append((nx, ny))
                nn = number[ny][nx]
                graph[n].append(nn)
                visited[ny][nx] = 0
                # graph[nn].append(n)
    return graph


def dfs(i, slide):
    if not graph[i]:
        dp[slide][i] = slide, None
        return slide

    r = dp[slide].get(i)
    if r is not None:
        return r[0]

    none = [dfs(c, 0) for c in graph[i]]
    if slide:
        r = sum(none)
        dp[slide][i] = r, None
        return r + 1
    else:
        to = [dfs(c, 1) for c in graph[i]]
        r = 0
        merge = None
        for i_ in range(len(graph[i])):
            s = 0
            for j_ in range(len(graph[i])):
                if j_ == i_: # slide!!
                    s += to[j_]
                else:
                    s += none[j_]
            if s > r:
                r = s
                merge = graph[i][i_]
        s = sum(none)
        if s > r:
            r = s
            merge = None
        dp[slide][i] = r, merge
        return r


def yx(i):
    return i // w + 1, i % w + 1


answers = []
def dfs_answer(i, slide):
    _, to = dp[slide][i]
    for c in graph[i]:
        if c == to:
            answers.append(yx(i) + yx(to))
            dfs_answer(c, 1)
        else:
            dfs_answer(c, 0)


for i in range(h):
    for j in range(w):
        if visited[i][j]:
            graph = bfs(j, i)
            dp = [{}, {}]
            dfs(number[i][j], 0)
            # print(dfs(number[i][j], 0), ":", j, i, number[i][j])
            #
            # print("--------")
            dfs_answer(number[i][j], 0)
            # __import__("sys").exit()

print(len(answers))
for ans in answers:
    print(*ans)

Buggy submission (verdict: Runtime Error):
import copy
h, w = map(int, input().split())

a = [list(map(lambda x: int(x) % 2, input().split())) for _ in range(h)]
# for v in a:
#     print(*v)

directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visited = copy.deepcopy(a)
number = [[i * w + j for j in range(w)] for i in range(h)]
def bfs(x, y):
    graph = [[] for _ in range(h * w)]
    que = [(x, y)]
    visited[y][x] = 0
    while que:
        x, y = que.pop(0)
        n = number[y][x]

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < w and 0 <= ny < h and visited[ny][nx] == 1:
                que.append((nx, ny))
                nn = number[ny][nx]
                graph[n].append(nn)
                visited[ny][nx] = 0
                # graph[nn].append(n)
    return graph


def dfs(i, slide):
    if not graph[i]:
        dp[slide][i] = slide, None
        return slide

    r = dp[slide].get(i)
    if r is not None:
        return r[0]

    none = [dfs(c, 0) for c in graph[i]]
    if slide:
        r = sum(none)
        dp[slide][i] = r, None
        return r + 1
    else:
        to = [dfs(c, 1) for c in graph[i]]
        r = 0
        merge = None
        for i_ in range(len(graph[i])):
            s = 0
            for j_ in range(len(graph[i])):
                if j_ == i_: # slide!!
                    s += to[j_]
                else:
                    s += none[j_]
            if s > r:
                r = s
                merge = graph[i][i_]
        s = sum(none)
        if s > r:
            r = s
            merge = None
        dp[slide][i] = r, merge
        return r


def xy(i):
    return i % w, i // w


answers = []
def dfs_answer(i, slide):
    _, to = dp[slide][i]
    for c in graph[i]:
        if c == to:
            answers.append(xy(i) + xy(to))
            dfs_answer(c, 1)
        else:
            dfs_answer(c, 0)


for i in range(h):
    for j in range(w):
        if visited[i][j]:
            graph = bfs(j, i)
            dp = [{}, {}]
            dfs(number[i][j], 0)
            # print(dfs(number[i][j], 0), ":", j, i, number[i][j])
            #
            # print("--------")
            dfs_answer(number[i][j], 0)
            # __import__("sys").exit()

print(len(answers))
for ans in answers:
    print(*ans)

Buggy submission (verdict: Runtime Error):
import copy
h, w = map(int, input().split())

a = [list(map(lambda x: int(x) % 2, input().split())) for _ in range(h)]
# for v in a:
#     print(*v)

directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visited = copy.deepcopy(a)
number = [[i * w + j for j in range(w)] for i in range(h)]
def bfs(x, y):
    graph = [[] for _ in range(h * w)]
    que = [(x, y)]
    visited[y][x] = 0
    while que:
        x, y = que.pop(0)
        n = number[y][x]

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < w and 0 <= ny < h and visited[ny][nx] == 1:
                que.append((nx, ny))
                nn = number[ny][nx]
                graph[n].append(nn)
                visited[ny][nx] = 0
                # graph[nn].append(n)
    return graph


def dfs(i, slide):
    if not graph[i]:
        dp[slide][i] = slide, None
        return slide

    r = dp[slide].get(i)
    if r is not None:
        return r[0]

    none = [dfs(c, 0) for c in graph[i]]
    if slide:
        r = sum(none)
        dp[slide][i] = r, None
        return r + 1
    else:
        to = [dfs(c, 1) for c in graph[i]]
        r = 0
        merge = None
        for i_ in range(len(graph[i])):
            s = 0
            for j_ in range(len(graph[i])):
                if j_ == i_: # slide!!
                    s += to[j_]
                else:
                    s += none[j_]
            if s > r:
                r = s
                merge = graph[i][i_]
        s = sum(none)
        if s > r:
            r = s
            merge = None
        dp[slide][i] = r, merge
        return r


def xy(i):
    return i % w, i // w


answers = []
def dfs_answer(i, slide):
    _, to = dp[slide][i]
    for c in graph[i]:
        if c == to:
            answers.append((*xy(i), *xy(to)))
            dfs_answer(c, 1)
        else:
            dfs_answer(c, 0)


for i in range(h):
    for j in range(w):
        if visited[i][j]:
            graph = bfs(j, i)
            dp = [{}, {}]
            dfs(number[i][j], 0)
            # print(dfs(number[i][j], 0), ":", j, i, number[i][j])
            #
            # print("--------")
            dfs_answer(number[i][j], 0)
            # __import__("sys").exit()

print(len(answers))
for ans in answers:
    print(*ans)