Problem p02579 (python)

Fixed submission:
h,w = map(int,input().split())
c = list(map(int,input().split()))
c[0] -= 1
c[1] -= 1
d = list(map(int,input().split()))
d[0] -= 1
d[1] -= 1
p = []
q = [[None for i in range(w)]for i in range(h)]
r = [[] for i in range(10**6)]
for i in range(h):
    s = input()
    s = list(s)
    p.append(s)
from collections import deque
de = deque()
de.append([c[0],c[1]])
q[c[0]][c[1]] = 0
g = 0
while q[d[0]][d[1]] == None and g < 10**6-3:
    while de:
        v = de.popleft()
        r[g].append([v[0],v[1]])
        for i in (-1,1):
            j = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
        for j in (-1,1):
            i = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
    g += 1
    while r[g-1]:
        v = r[g-1].pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if (abs(i) == 1 and j == 0) or (abs(j) == 1 and i == 0):
                    continue
                else:
                    if 0 <= v[0]-i <= h-1:
                        if 0 <= v[1]-j <= w-1:
                            if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                                q[v[0]-i][v[1]-j] = g
                                de.append([v[0]-i,v[1]-j])
if q[d[0]][d[1]] == None:
    print(-1)
else:
    print(q[d[0]][d[1]])

Buggy submission (verdict: Runtime Error):
h,w = map(int,input().split())
c = list(map(int,input().split()))
c[0] -= 1
c[1] -= 1
d = list(map(int,input().split()))
d[0] -= 1
d[1] -= 1
p = []
q = [[None for i in range(w)]for i in range(h)]
r = [[] for i in range(10**6)]
for i in range(h):
    s = input()
    s = list(s)
    p.append(s)
from collections import deque
de = deque()
de.append([c[0],c[1]])
q[c[0]][c[1]] = 0
g = 0
while q[d[0]][d[1]] == None and g < 10**6-3:
    while de:
        v = de.popleft()
        r[g].append([v[0],v[1]])
        for i in (-1,1):
            j = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
        for j in (-1,1):
            i = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
    g += 1
    while r[g-1]:
        v = r[g-1].pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if (abs(i) == 1 and j = 0 ) or (abs(j) == 1 and i == 0)
                    continue
                else:
                    if 0 <= v[0]-i <= h-1:
                        if 0 <= v[1]-j <= w-1:
                            if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                                q[v[0]-i][v[1]-j] = g
                                de.append([v[0]-i,v[1]-j])
if q[d[0]][d[1]] == None:
    print(-1)
else:
    print(q[d[0]][d[1]])