Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]


def bfs0(white_cells, black_cells):

    while white_cells:
        h, w = white_cells.popleft()
        if h==0 and w==0 and grid[h][w] == "#":
            black_cells.append((h, w))
            return black_cells

        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == ".":
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == ".":
                    return 1
                else:
                    return 0

    return black_cells


def bfs1(black_cells, white_cells):

    while black_cells:
        h, w = black_cells.popleft()
        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == "#":
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == "#":
                    return 1
                else:
                    return 0

    return white_cells

count = 0
ans = 0

if count == 0:
    white_cells = deque()
    white_cells.append((0, 0))
    black_cells = deque()

while black_cells != 1 and white_cells != 1 and black_cells != 0 and white_cells != 0:
    if count % 2 == 0:
        a = 1
        temp_black_cells = bfs0(white_cells, black_cells)
        black_cells = temp_black_cells
        ans += 1
    else:
        a = 0
        temp_white_cells = bfs1(black_cells, white_cells)
        white_cells = temp_white_cells
    count += 1

if black_cells == 1:
    ans -=1

print(ans)

Fixed submission:
from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]


def bfs0(white_cells, black_cells):

    while white_cells:
        h, w = white_cells.popleft()
        if h==0 and w==0 and grid[h][w] == "#":
            black_cells.append((h, w))
            return black_cells

        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == ".":
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == ".":
                    return 1
                else:
                    return 0

    return black_cells


def bfs1(black_cells, white_cells):

    while black_cells:
        h, w = black_cells.popleft()
        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == "#":
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == "#":
                    return 1
                else:
                    return 0

    return white_cells

count = 0
ans = 0

if count == 0:
    white_cells = deque()
    white_cells.append((0, 0))
    black_cells = deque()

while black_cells != 1 and white_cells != 1 and black_cells != 0 and white_cells != 0:
    if count % 2 == 0:
        a = 1
        temp_black_cells = bfs0(white_cells, black_cells)
        black_cells = temp_black_cells
        ans += 1
    else:
        a = 0
        temp_white_cells = bfs1(black_cells, white_cells)
        white_cells = temp_white_cells
    count += 1

if black_cells == 1:
    ans -=1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]


def bfs0(white_cells, black_cells):

    while white_cells:
        h, w = white_cells.popleft()
        if h==0 and w==0 and grid[h][w] == "#":
            black_cells.append((h, w))
            return black_cells

        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == ".":
                    return 1
                else:
                    return 0
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == ".":
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))

    return black_cells


def bfs1(black_cells, white_cells):

    while black_cells:
        h, w = black_cells.popleft()
        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == "#":
                    return 1
                else:
                    return 0
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == "#":
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))

    return white_cells

count = 0
ans = 0

if count == 0:
    white_cells = deque()
    white_cells.append((0, 0))
    black_cells = deque()

while black_cells != 1 and white_cells != 1 and black_cells != 0 and white_cells != 0:
    if count % 2 == 0:
        a = 1
        temp_black_cells = bfs0(white_cells, black_cells)
        black_cells = temp_black_cells
        if black_cells != 1 and white_cells != 1:
            ans += 1
    else:
        a = 0
        temp_white_cells = bfs1(black_cells, white_cells)
        white_cells = temp_white_cells
    count += 1





print(ans)

Fixed submission:
from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]


def bfs0(white_cells, black_cells):

    while white_cells:
        h, w = white_cells.popleft()
        if h==0 and w==0 and grid[h][w] == "#":
            black_cells.append((h, w))
            return black_cells

        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == ".":
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == ".":
                    return 1
                else:
                    return 0

    return black_cells


def bfs1(black_cells, white_cells):

    while black_cells:
        h, w = black_cells.popleft()
        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == "#":
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == "#":
                    return 1
                else:
                    return 0

    return white_cells

count = 0
ans = 0

if count == 0:
    white_cells = deque()
    white_cells.append((0, 0))
    black_cells = deque()

while black_cells != 1 and white_cells != 1 and black_cells != 0 and white_cells != 0:
    if count % 2 == 0:
        a = 1
        temp_black_cells = bfs0(white_cells, black_cells)
        black_cells = temp_black_cells
        ans += 1
    else:
        a = 0
        temp_white_cells = bfs1(black_cells, white_cells)
        white_cells = temp_white_cells
    count += 1

if black_cells == 1:
    ans -=1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]


def bfs0(white_cells, black_cells):

    while white_cells:
        h, w = white_cells.popleft()
        if h==0 and w==0 and grid[h][w] == "#":
            black_cells.append((h, w))
            return black_cells

        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == ".":
                    return 1
                else:
                    return 0
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == ".":
                white_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))

    return black_cells


def bfs1(black_cells, white_cells):

    while black_cells:
        h, w = black_cells.popleft()
        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == "#":
                    return 1
                else:
                    return 0
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == "#":
                black_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))

    return white_cells

count = 0
ans = 0

if count == 0:
    white_cells = deque()
    white_cells.append((0, 0))
    black_cells = deque()

while black_cells != 1 and white_cells != 1 and black_cells != 0 and white_cells != 0:
    if count % 2 == 0:
        a = 1
        temp_black_cells = bfs0(white_cells, black_cells)
        black_cells = temp_black_cells
        if black_cells != 1 and white_cells != 1:
            ans += 1
    else:
        a = 0
        temp_white_cells = bfs1(black_cells, white_cells)
        white_cells = temp_white_cells
    count += 1

print(ans)

Fixed submission:
from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]


def bfs0(white_cells, black_cells):

    while white_cells:
        h, w = white_cells.popleft()
        if h==0 and w==0 and grid[h][w] == "#":
            black_cells.append((h, w))
            return black_cells

        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == ".":
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == ".":
                    return 1
                else:
                    return 0

    return black_cells


def bfs1(black_cells, white_cells):

    while black_cells:
        h, w = black_cells.popleft()
        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == "#":
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == "#":
                    return 1
                else:
                    return 0

    return white_cells

count = 0
ans = 0

if count == 0:
    white_cells = deque()
    white_cells.append((0, 0))
    black_cells = deque()

while black_cells != 1 and white_cells != 1 and black_cells != 0 and white_cells != 0:
    if count % 2 == 0:
        a = 1
        temp_black_cells = bfs0(white_cells, black_cells)
        black_cells = temp_black_cells
        ans += 1
    else:
        a = 0
        temp_white_cells = bfs1(black_cells, white_cells)
        white_cells = temp_white_cells
    count += 1

if black_cells == 1:
    ans -=1

print(ans)