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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
dh -= 1
dw -= 1
check[ch][cw] = 0
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
magic1 = [[1, 1], [1, -1], [2, 2], [2, 1], [2, 0], [2, -1], [2, -1]]
magic2 = [[-1, 1], [-1, -1], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -1]]
magic3 = [[1, 1], [-1, 1], [2, 2], [1, 2], [0, 2], [-1, 2], [-2, 2]]
magic4 = [[1, -1], [-1, -1], [2, -2], [1, -2], [0, -2], [-1, -2], [-2, -2]]

queue.append([ch, cw])
queue.append(0)
while queue:
    pos = queue.popleft()
    dd = queue.popleft()
    if check[pos[0]][pos[1]] < dd:
        continue
    flg = [False, False, False, False]
    for dy, dx in walk:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            if dy == 1:
                flg[0] = True
            elif dy == -1:
                flg[1] = True
            elif dx == 1:
                flg[2] = True
            else:
                flg[3] = True
            continue
        check[n_h][n_w] = dd
        queue.append([n_h, n_w])
        queue.append(dd)
        
    if flg[0]:
        for dy, dx in magic1:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[1]:
        for dy, dx in magic2:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[2]:
        for dy, dx in magic3:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[3]:
        for dy, dx in magic4:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)

if check[dh][dw] == inf:
    print(-1)
else:
    print(check[dh][dw])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
lh, lw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
lh -= 1
lw -= 1
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]

queue.append([ch, cw])
d = 0

while queue:
    queue2 = queue.copy()
    queue = deque()
    while queue2:
        pos = queue2.popleft()
        flg = [False, False, False, False]
        for dh, dw in walk:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                if dh == 1:
                    flg[0] = True
                elif dh == -1:
                    flg[1] = True
                elif dw == 1:
                    flg[2] = True
                else:
                    flg[3] = True
                continue
            if check[n_h][n_w] <= d:
                continue
            check[n_h][n_w] = d
            queue2.append([n_h, n_w])
            
        magic = []
        if flg[0]:
            magic.append([2, 0])
            if flg[2]:
                magic.append([2, 1])
                magic.append([2, 2])
                magic.append([1, 2])
                magic.append([1, 1])
            if flg[3]:
                magic.append([2, -1])
                magic.append([2, -2])
                magic.append([1, -2])
                magic.append([1, -1])
        if flg[1]:
            magic.append([-2, 0])
            if flg[2]:
                magic.append([-2, 1])
                magic.append([-2, 2])
                magic.append([-1, 2])
                magic.append([-1, 1])
            if flg[3]:
                magic.append([-2, -1])
                magic.append([-2, -2])
                magic.append([-1, -2])
                magic.append([-1, -1])
        if flg[2]:
            magic.append([0, 2])
        if flg[3]:
            magic.append([0, -2])
            
        for dh, dw in magic:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            if check[n_h][n_w] <= d + 1:
                continue
            check[n_h][n_w] = d + 1
            queue.append([n_h, n_w])
    d += 1

if check[lh][lw] == inf:
    print(-1)
else:
    print(check[lh][lw])

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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
dh -= 1
dw -= 1
check[ch][cw] = 0
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
magic1 = [[1, 1], [1, -1], [2, 2], [2, 1], [2, 0], [2, -1], [2, -1]]
magic2 = [[-1, 1], [-1, -1], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -1]]
magic3 = [[1, 1], [-1, 1], [2, 2], [1, 2], [0, 2], [-1, 2], [-2, 2]]
magic4 = [[1, -1], [-1, -1], [2, -2], [1, -2], [0, -2], [-1, -2], [-2, -2]]

queue.append([ch, cw])
queue.append(0)
while queue:
    pos = queue.popleft()
    dd = queue.popleft()
    flg = [False, False, False, False]
    for dy, dx in walk:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            if dy == 1:
                flg[0] = True
            elif dy == -1:
                flg[1] = True
            elif dx == 1:
                flg[2] = True
            else:
                flg[3] = True
            continue
        check[n_h][n_w] = dd
        queue.append([n_h, n_w])
        queue.append(dd)
        
    if flg[0]:
        for dy, dx in magic1:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[1]:
        for dy, dx in magic2:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[2]:
        for dy, dx in magic3:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[3]:
        for dy, dx in magic4:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)

if check[dh][dw] == inf:
    print(-1)
else:
    print(check[dh][dw])

Fixed submission:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
lh, lw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
lh -= 1
lw -= 1
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]

queue.append([ch, cw])
d = 0

while queue:
    queue2 = queue.copy()
    queue = deque()
    while queue2:
        pos = queue2.popleft()
        flg = [False, False, False, False]
        for dh, dw in walk:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                if dh == 1:
                    flg[0] = True
                elif dh == -1:
                    flg[1] = True
                elif dw == 1:
                    flg[2] = True
                else:
                    flg[3] = True
                continue
            if check[n_h][n_w] <= d:
                continue
            check[n_h][n_w] = d
            queue2.append([n_h, n_w])
            
        magic = []
        if flg[0]:
            magic.append([2, 0])
            if flg[2]:
                magic.append([2, 1])
                magic.append([2, 2])
                magic.append([1, 2])
                magic.append([1, 1])
            if flg[3]:
                magic.append([2, -1])
                magic.append([2, -2])
                magic.append([1, -2])
                magic.append([1, -1])
        if flg[1]:
            magic.append([-2, 0])
            if flg[2]:
                magic.append([-2, 1])
                magic.append([-2, 2])
                magic.append([-1, 2])
                magic.append([-1, 1])
            if flg[3]:
                magic.append([-2, -1])
                magic.append([-2, -2])
                magic.append([-1, -2])
                magic.append([-1, -1])
        if flg[2]:
            magic.append([0, 2])
        if flg[3]:
            magic.append([0, -2])
            
        for dh, dw in magic:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            if check[n_h][n_w] <= d + 1:
                continue
            check[n_h][n_w] = d + 1
            queue.append([n_h, n_w])
    d += 1

if check[lh][lw] == inf:
    print(-1)
else:
    print(check[lh][lw])

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


h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
tizu = [input() for _ in range(h)]
inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
dh -= 1
dw -= 1
check[ch][cw] = 0
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
magic = [[1, 1], [-1, 1], [1, -1], [-1, -1], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]
    ,[1, -2], [1, 2], [0, -2], [0, 2], [-1, -2], [-1, 2], [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2]]

queue.append([ch, cw])
queue.append(0)
while queue:
    pos = queue.popleft()
    dd = queue.popleft()
    flg = False
    for dy, dx in walk:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            flg = True
            continue
        check[n_h][n_w] = dd
        queue.append([n_h, n_w])
        queue.append(dd)
        
    if flg:
        for dy, dx in magic:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)

if check[dh][dw] == inf:
    print(-1)
else:
    print(check[dh][dw])

Fixed submission:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
lh, lw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
lh -= 1
lw -= 1
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]

queue.append([ch, cw])
d = 0

while queue:
    queue2 = queue.copy()
    queue = deque()
    while queue2:
        pos = queue2.popleft()
        flg = [False, False, False, False]
        for dh, dw in walk:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                if dh == 1:
                    flg[0] = True
                elif dh == -1:
                    flg[1] = True
                elif dw == 1:
                    flg[2] = True
                else:
                    flg[3] = True
                continue
            if check[n_h][n_w] <= d:
                continue
            check[n_h][n_w] = d
            queue2.append([n_h, n_w])
            
        magic = []
        if flg[0]:
            magic.append([2, 0])
            if flg[2]:
                magic.append([2, 1])
                magic.append([2, 2])
                magic.append([1, 2])
                magic.append([1, 1])
            if flg[3]:
                magic.append([2, -1])
                magic.append([2, -2])
                magic.append([1, -2])
                magic.append([1, -1])
        if flg[1]:
            magic.append([-2, 0])
            if flg[2]:
                magic.append([-2, 1])
                magic.append([-2, 2])
                magic.append([-1, 2])
                magic.append([-1, 1])
            if flg[3]:
                magic.append([-2, -1])
                magic.append([-2, -2])
                magic.append([-1, -2])
                magic.append([-1, -1])
        if flg[2]:
            magic.append([0, 2])
        if flg[3]:
            magic.append([0, -2])
            
        for dh, dw in magic:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            if check[n_h][n_w] <= d + 1:
                continue
            check[n_h][n_w] = d + 1
            queue.append([n_h, n_w])
    d += 1

if check[lh][lw] == inf:
    print(-1)
else:
    print(check[lh][lw])

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


h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
tizu = [input() for _ in range(h)]
inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
dh -= 1
dw -= 1
check[ch][cw] = 0
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
magic = [[1, 1], [-1, 1], [1, -1], [-1, -1], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]
    ,[1, -2], [1, 2], [0, -2], [0, 2], [-1, -2], [-1, 2], [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2]]

queue.append([ch, cw])
queue.append(0)
while queue:
    pos = queue.popleft()
    dd = queue.popleft()
    flg = False
    for dy, dx in walk:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            flg = True
            continue
        check[n_h][n_w] = dd
        queue.append([n_h, n_w])
        queue.append(dd)
        
    if flg:
        for dy, dx in magic:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)

if check[dh][dw] == inf:
    print(-1)
else:
    print(check[dh][dw])

Fixed submission:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
lh, lw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
lh -= 1
lw -= 1
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]

queue.append([ch, cw])
d = 0

while queue:
    queue2 = queue.copy()
    queue = deque()
    while queue2:
        pos = queue2.popleft()
        flg = [False, False, False, False]
        for dh, dw in walk:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                if dh == 1:
                    flg[0] = True
                elif dh == -1:
                    flg[1] = True
                elif dw == 1:
                    flg[2] = True
                else:
                    flg[3] = True
                continue
            if check[n_h][n_w] <= d:
                continue
            check[n_h][n_w] = d
            queue2.append([n_h, n_w])
            
        magic = []
        if flg[0]:
            magic.append([2, 0])
            if flg[2]:
                magic.append([2, 1])
                magic.append([2, 2])
                magic.append([1, 2])
                magic.append([1, 1])
            if flg[3]:
                magic.append([2, -1])
                magic.append([2, -2])
                magic.append([1, -2])
                magic.append([1, -1])
        if flg[1]:
            magic.append([-2, 0])
            if flg[2]:
                magic.append([-2, 1])
                magic.append([-2, 2])
                magic.append([-1, 2])
                magic.append([-1, 1])
            if flg[3]:
                magic.append([-2, -1])
                magic.append([-2, -2])
                magic.append([-1, -2])
                magic.append([-1, -1])
        if flg[2]:
            magic.append([0, 2])
        if flg[3]:
            magic.append([0, -2])
            
        for dh, dw in magic:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            if check[n_h][n_w] <= d + 1:
                continue
            check[n_h][n_w] = d + 1
            queue.append([n_h, n_w])
    d += 1

if check[lh][lw] == inf:
    print(-1)
else:
    print(check[lh][lw])

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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
tizu = [input() for _ in range(h)]
inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
dh -= 1
dw -= 1
check[ch][cw] = 0
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
magic = [[1, 1], [-1, 1], [1, -1], [-1, -1], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]
    ,[1, -2], [1, 2], [0, -2], [0, 2], [-1, -2], [-1, 2], [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2]]

queue.append([ch, cw])
queue.append(0)
while queue:
    pos = queue.popleft()
    dd = queue.popleft()
    for dy, dx in walk:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            continue
        check[n_h][n_w] = dd
        queue.append([n_h, n_w])
        queue.append(dd)

    for dy, dx in magic:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            continue
        check[n_h][n_w] = dd + 1
        queue.append([n_h, n_w])
        queue.append(dd + 1)

if check[dh][dw] == inf:
    print(-1)
else:
    print(check[dh][dw])

Fixed submission:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
lh, lw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
lh -= 1
lw -= 1
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]

queue.append([ch, cw])
d = 0

while queue:
    queue2 = queue.copy()
    queue = deque()
    while queue2:
        pos = queue2.popleft()
        flg = [False, False, False, False]
        for dh, dw in walk:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                if dh == 1:
                    flg[0] = True
                elif dh == -1:
                    flg[1] = True
                elif dw == 1:
                    flg[2] = True
                else:
                    flg[3] = True
                continue
            if check[n_h][n_w] <= d:
                continue
            check[n_h][n_w] = d
            queue2.append([n_h, n_w])
            
        magic = []
        if flg[0]:
            magic.append([2, 0])
            if flg[2]:
                magic.append([2, 1])
                magic.append([2, 2])
                magic.append([1, 2])
                magic.append([1, 1])
            if flg[3]:
                magic.append([2, -1])
                magic.append([2, -2])
                magic.append([1, -2])
                magic.append([1, -1])
        if flg[1]:
            magic.append([-2, 0])
            if flg[2]:
                magic.append([-2, 1])
                magic.append([-2, 2])
                magic.append([-1, 2])
                magic.append([-1, 1])
            if flg[3]:
                magic.append([-2, -1])
                magic.append([-2, -2])
                magic.append([-1, -2])
                magic.append([-1, -1])
        if flg[2]:
            magic.append([0, 2])
        if flg[3]:
            magic.append([0, -2])
            
        for dh, dw in magic:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            if check[n_h][n_w] <= d + 1:
                continue
            check[n_h][n_w] = d + 1
            queue.append([n_h, n_w])
    d += 1

if check[lh][lw] == inf:
    print(-1)
else:
    print(check[lh][lw])