Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from sys import stdin
from collections import deque


read = stdin.buffer.read
readline = stdin.buffer.readline
readlines = stdin.buffer.readlines

q = deque()

h, w = map(int, readline().split())
ch, cw = map(int, readline().split())
dh, dw = map(int, readline().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

INF = 10 ** 18
org_list = deque()
cost_list = [[INF]*w for i in range(h)]

# for i in range(h):
#   # 文字列の入力
#   s = stdin.readline()
#   org_list.append(s)


org_list=list(map(lambda x: list(x.decode()), readlines()))

cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
# ido_h = [-1, 0, 1, 0]
# ido_w = [0, 1, 0, -1]
ido_x = [[-1, 0], [0, 1], [1, 0], [0, -1]]

magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]


  for ih, iw in ido_x:
    nh = ph + ih
    nw = pw + iw


  # for i in range(4):
  #   nh = ph + ido_h[i]
  #   nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]


    if val == "#" or val_cost <= cost:
      continue

    cost_list[nh][nw] = cost
    q.appendleft([nh, nw])


  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from sys import stdin
from collections import deque


read = stdin.buffer.read
readline = stdin.buffer.readline
readlines = stdin.buffer.readlines

q = deque()

h, w = map(int, readline().split())
ch, cw = map(int, readline().split())
dh, dw = map(int, readline().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

INF = 10 ** 18
org_list = deque()
cost_list = [[INF]*w for i in range(h)]

# for i in range(h):
#   # 文字列の入力
#   s = stdin.readline()
#   org_list.append(s)


org_list=list(map(lambda x: list(x.decode()), readlines()))

cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
# ido_h = [-1, 0, 1, 0]
# ido_w = [0, 1, 0, -1]
ido_x = [[-1, 0], [0, 1], [1, 0], [0, -1]]

magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]


  for ih, iw in ido_x:
    nh = ph + ih
    nw = pw + iw


  # for i in range(4):
  #   nh = ph + ido_h[i]
  #   nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]


    if val == "#" or val_cost <= cost:
      continue

    cost_list[nh][nw] = cost
    q.appendleft([nh, nw])


  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from sys import stdin
from collections import deque


read = stdin.buffer.read
readline = stdin.buffer.readline
readlines = stdin.buffer.readlines

q = deque()

h, w = map(int, readline().split())
ch, cw = map(int, readline().split())
dh, dw = map(int, readline().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

INF = 10 ** 18
org_list = deque()
cost_list = [[INF]*w for i in range(h)]

# for i in range(h):
#   # 文字列の入力
#   s = stdin.readline()
#   org_list.append(s)


org_list=list(map(lambda x: list(x.decode()), readlines()))

cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]

    # if val == "#" or val_cost == cost:
    #   continue
    # if val == "." or val_cost < val:
    #   cost_list[nh][nw] = cost
    #   q.appendleft([nh, nw])


    if val == "#" or val_cost <= cost:
      continue

    cost_list[nh][nw] = cost
    q.appendleft([nh, nw])


  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

# import numpy as np
# from numba import njit

from sys import stdin
from collections import deque

def mytest():

  q = deque()

  h, w = map(int, input().split())
  ch, cw = map(int, input().split())
  dh, dw = map(int, input().split())

  ch -= 1
  cw -= 1
  dh -= 1
  dw -= 1

  INF = 10 ** 18
  org_list = deque()
  cost_list = [[INF]*w for i in range(h)]

  for _ in range(h):
    org_list.append(stdin.readline())

  cost_list[ch][cw] = 0

  cost = 0
  ph = ch
  pw = cw

  q.append([ph, pw])

  # 上右下左
  ido_h = [-1, 0, 1, 0]
  ido_w = [0, 1, 0, -1]

  magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
  while q:

    ph, pw = q.popleft()
    cost = cost_list[ph][pw]

    for i in range(4):
      nh = ph + ido_h[i]
      nw = pw + ido_w[i]

      if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
        continue
      val = org_list[nh][nw]
      val_cost = cost_list[nh][nw]

      if val == "#" or val_cost <= cost:
        continue

      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])

    # ワープ
    for ih, iw in magic:
      nh = ph + ih
      nw = pw + iw
      if nh < 0 or h -1 < nh:
        continue
      if nw < 0 or w -1 < nw:
        continue
      if cost_list[nh][nw] <= cost:
        continue

      if org_list[nh][nw] == ".":
        cost_list[nh][nw] = cost + 1
        q.append([nh, nw])

  result = cost_list[dh][dw]
  if result == INF:
    result = -1

  print(result)

mytest()


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

# import numpy as np
# from numba import njit

from sys import stdin
from collections import deque

def mytest():

  q = deque()

  h, w = map(int, input().split())
  ch, cw = map(int, input().split())
  dh, dw = map(int, input().split())

  ch -= 1
  cw -= 1
  dh -= 1
  dw -= 1

  INF = 10 ** 18
  org_list = deque()
  cost_list = [[INF]*w for i in range(h)]

  for _ in range(h):
    org_list.append(stdin.readline())

  cost_list[ch][cw] = 0

  cost = 0
  ph = ch
  pw = cw

  q.append([ph, pw])

  # 上右下左
  ido_h = [-1, 0, 1, 0]
  ido_w = [0, 1, 0, -1]

  magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
  while q:

    ph, pw = q.popleft()
    cost = cost_list[ph][pw]

    for i in range(4):
      nh = ph + ido_h[i]
      nw = pw + ido_w[i]

      if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
        continue
      val = org_list[nh][nw]
      val_cost = cost_list[nh][nw]

      if val == "#" or val_cost <= cost:
        continue

      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])

    # ワープ
    for ih, iw in magic:
      nh = ph + ih
      nw = pw + iw
      if nh < 0 or h -1 < nh:
        continue
      if nw < 0 or w -1 < nw:
        continue
      if cost_list[nh][nw] <= cost:
        continue

      if org_list[nh][nw] == ".":
        cost_list[nh][nw] = cost + 1
        q.append([nh, nw])

  result = cost_list[dh][dw]
  if result == INF:
    result = -1

  print(result)

mytest()


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

import numpy as np
from numba import njit

from sys import stdin
from collections import deque

@njit(cache=True)
def mytest():

  q = deque()

  h, w = map(int, input().split())
  ch, cw = map(int, input().split())
  dh, dw = map(int, input().split())

  ch -= 1
  cw -= 1
  dh -= 1
  dw -= 1


  INF = 10 ** 18
  org_list = deque()
  cost_list = [[INF]*w for i in range(h)]

  for i in range(h):
    # 文字列の入力
    s = stdin.readline()
    org_list.append(s)





  cost_list[ch][cw] = 0

  cost = 0
  ph = ch
  pw = cw

  q.append([ph, pw])

  # 上右下左
  ido_h = [-1, 0, 1, 0]
  ido_w = [0, 1, 0, -1]

  magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
  while q:

    ph, pw = q.popleft()
    cost = cost_list[ph][pw]

    for i in range(4):
      nh = ph + ido_h[i]
      nw = pw + ido_w[i]

      if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
        continue
      val = org_list[nh][nw]
      val_cost = cost_list[nh][nw]

      if val == "#" or val_cost <= cost:
        continue

      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])


    # ワープ
    for ih, iw in magic:
      nh = ph + ih
      nw = pw + iw
      if nh < 0 or h -1 < nh:
        continue
      if nw < 0 or w -1 < nw:
        continue
      if cost_list[nh][nw] <= cost:
        continue

      if org_list[nh][nw] == ".":
        cost_list[nh][nw] = cost + 1
        q.append([nh, nw])

  result = cost_list[dh][dw]
  if result == INF:
    result = -1

  # # 最後デバッグ
  # for li in org_list:
  #   print(li)
  # for li in cost_list:
  #   print(li)


  print(result)

mytest()


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from sys import stdin
from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# m=list(map(lambda x: list(x.decode()), stdin.readlines()))
# org_list = stdin.readlines()
# print(org_list)

INF = 10 ** 18
# org_list = [INF for i in range(h)]
org_list = deque()
# cost_list = [[INF for j in range(w)] for i in range(h)]
cost_list = [[INF]*w for i in range(h)]

for i in range(h):
  # 文字列の入力
  s = stdin.readline()
  org_list.append(s)


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]

    # if val == "#" or val_cost == cost:
    #   continue
    # if val == "." or val_cost < val:
    #   cost_list[nh][nw] = cost
    #   q.appendleft([nh, nw])


    if val == "#" or val_cost <= cost:
      continue

    cost_list[nh][nw] = cost
    q.appendleft([nh, nw])


  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from sys import stdin
from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

INF = 10 ** 18
# org_list = [INF for i in range(h)]
org_list = deque()
# cost_list = [[INF for j in range(w)] for i in range(h)]
cost_list = [[INF]*w for i in range(h)]

for i in range(h):
  # 文字列の入力
  # s = input()
  s = stdin.readline()
  org_list.append(s)


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]
    if val == "#" or val_cost == cost:
      continue
    if val == "." or val_cost < val:
      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])

  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

INF = 10 ** 18
# org_list = [INF for i in range(h)]
org_list = deque()
# cost_list = [[INF for j in range(w)] for i in range(h)]
cost_list = [[INF]*w for i in range(h)]

for i in range(h):
  # 文字列の入力
  s = input()
  # org_list[i] = s
  org_list.append(s)


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]
    if val == "#" or val_cost == cost:
      continue
    if val == "." or val_cost < val:
      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])

  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

  # # ジャンプ--------------
  # for i in range(-2, 3):
  #   if (ph + i < 0) or (h - 1 < ph + i):
  #     continue

  #   for j in range(-2, 3):
  #     if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
  #       continue
  #     if cost_list[ph + i][pw + j] <= cost:
  #       continue
  #     if org_list[ph + i][pw + j] == ".":
  #       cost_list[ph + i][pw + j] = cost + 1
  #       q.append([ph + i, pw + j])



result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

INF = 10 ** 18
# org_list = [INF for i in range(h)]
org_list = deque()
# cost_list = [[INF for j in range(w)] for i in range(h)]
cost_list = [[INF]*w for i in range(h)]

for i in range(h):
  # 文字列の入力
  s = input()
  # org_list[i] = s
  org_list.append(s)


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]
    if val == "#" or val_cost == cost:
      continue
    if val == "." or val_cost < val:
      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])

  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if cost_list[ph + i][pw + j] <= cost:
        continue
      if org_list[ph + i][pw + j] == ".":
        cost_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

INF = 10 ** 18
# org_list = [INF for i in range(h)]
org_list = deque()
cost_list = [[INF for j in range(w)] for i in range(h)]


for i in range(h):
  # 文字列の入力
  s = input()
  # org_list[i] = s
  org_list.append(s)


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]
    if val == "#" or val_cost == cost:
      continue
    if val == "." or val_cost < val:
      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])

  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if cost_list[ph + i][pw + j] <= cost:
        continue
      if org_list[ph + i][pw + j] == ".":
        cost_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

INF = 10 ** 18
org_list = [INF for i in range(h)]
cost_list = [[INF for j in range(w)] for i in range(h)]


for i in range(h):
  # 文字列の入力
  s = input()
  org_list[i] = s


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

# loopc = 3
# while 0 < loopc:
while q:

  # print("-------------")
  # loopc -= 1

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  # print(ph, pw, cost)

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]
    if val == "#" or val_cost == cost:
      continue
    if val == "." or val_cost < val:
      cost_list[nh][nw] = cost
      # print("４ついか")
      q.appendleft([nh, nw])



  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if cost_list[ph + i][pw + j] <= cost:
        continue
      if org_list[ph + i][pw + j] == ".":
        cost_list[ph + i][pw + j] = cost + 1
        # print("jついか")
        q.append([ph + i, pw + j])


  # 最後デバッグ
  # for li in org_list:
  # #   print(li)
  # for li in cost_list:
  #   print(li)

  # print(q)

  # loop = False

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

ban_list = [[-999 for j in range(w)] for i in range(h)]


for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]


ban_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

while q:
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = ban_list[nh][nw]
    if val == "#" or val == cost:
      continue
    if val == "." or cost < val:
      ban_list[nh][nw] = cost
      q.appendleft([nh, nw])



  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])


result = ban_list[dh][dw]
if result == ".":
  result = -1


print(result)


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)


Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque

q = deque()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

# mylist = [[]]
ban_list = [[-1 for j in range(w)] for i in range(h)]
cost_list = [[-1 for j in range(w)] for i in range(h)]

# print(mylist)

for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0
# cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])


# # 最後デバッグ
# for li in ban_list:
#   print(li)



loop = True
while loop:
  # print(len(q))
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  # print(ph, pw)
  # print(cost)
  # 上
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        # appendだとrandom_02.txtがWAになる
        q.appendleft([ph-1, pw])
    else:
      pass

  # 右
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  # 下
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  # 左
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        # print(ph, pw)
        # print(i, j)
        # print(cost)
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1

# # 最後デバッグ
# for li in ban_list:
#   print(li)

print(result)