Problem:
 Score : 400 points    Problem Statement A maze is composed of a grid of H \times W squares - H vertical, W horizontal.  The square at the i -th row from the top and the j -th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is . .  There is a magician in (C_h,C_w) . He can do the following two kinds of moves:   Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.  Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.   In either case, he cannot go out of the maze.  At least how many times does he need to use the magic to reach (D_h, D_w) ?      Constraints  1 \leq H,W \leq 10^3  1 \leq C_h,D_h \leq H  1 \leq C_w,D_w \leq W  S_{ij} is # or . .  S_{C_h C_w} and S_{D_h D_w} are . .  (C_h,C_w) \neq (D_h,D_w)         Input Input is given from Standard Input in the following format:  H  W  C_h  C_w  D_h  D_w  S_{11}\ldots S_{1W}  \vdots  S_{H1}\ldots S_{HW}       Output Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w) , print -1 instead.        Sample Input 1 4 4
1 1
4 4
..#.
..#.
.#..
.#..      Sample Output 1 1  For example, by walking to (2,2) and then using the magic to travel to (4,4) , just one use of magic is enough.  Note that he cannot walk diagonally.       Sample Input 2 4 4
1 4
4 1
.##.
####
####
.##.      Sample Output 2 -1  He cannot move from there.       Sample Input 3 4 4
2 2
3 3
....
....
....
....      Sample Output 3 0  No use of magic is needed.       Sample Input 4 4 5
1 2
2 5
#.###
####.
#..##
#..##      Sample Output 4 2

Solution (Python):
import base64

exec(base64.b64decode(b'aW1wb3J0IHN1YnByb2Nlc3MKaW1wb3J0IHN5cwoKY29kZSA9IHIiIiIjaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPGNocm9ubz4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y29tcGxleD4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPHJhbmRvbT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dHVwbGU+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8dmVjdG9yPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnVzaW5nIGludDY0ID0gbG9uZyBsb25nOwoKI2RlZmluZSBhbGwoJCkgYmVnaW4oJCksIGVuZCgkKQojZGVmaW5lIHJhbGwoJCkgcmJlZ2luKCQpLCByZW5kKCQpCgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KaW5saW5lIHZvaWQgZXJhcXVlKHN0ZDo6dmVjdG9yPFQ+JiB2ZWMpIHsKICB2ZWMuZXJhc2Uoc3RkOjp1bmlxdWUodmVjLmJlZ2luKCksIHZlYy5lbmQoKSksIHZlYy5lbmQoKSk7CiAgcmV0dXJuOwp9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KaW5saW5lIGludCBsb3dlcl9wb3NpdGlvbihjb25zdCBzdGQ6OnZlY3RvcjxUPiYgdmVjLCBUIHZhbCkgewogIHJldHVybiBzdGF0aWNfY2FzdDxpbnQ+KHN0ZDo6ZGlzdGFuY2UoCiAgICAgIHZlYy5iZWdpbigpLCBzdGQ6Omxvd2VyX2JvdW5kKHZlYy5iZWdpbigpLCB2ZWMuZW5kKCksIHZhbCkpKTsKfQoKdGVtcGxhdGUgPGNsYXNzIFQ+CmlubGluZSBpbnQgdXBwZXJfcG9zaXRpb24oY29uc3Qgc3RkOjp2ZWN0b3I8VD4mIHZlYywgVCB2YWwpIHsKICByZXR1cm4gc3RhdGljX2Nhc3Q8aW50PihzdGQ6OmRpc3RhbmNlKAogICAgICB2ZWMuYmVnaW4oKSwgc3RkOjp1cHBlcl9ib3VuZCh2ZWMuYmVnaW4oKSwgdmVjLmVuZCgpLCB2YWwpKSk7Cn0KCnRlbXBsYXRlIDxjbGFzcyBUPgppbmxpbmUgc3RkOjpzdHJpbmcgdG9fYmluYXJ5KFQgbikgewogIGFzc2VydChuID4gMCk7CiAgc3RkOjpzdHJpbmcgcmV0ID0gIiI7CiAgd2hpbGUgKG4pIHJldCArPSAobiAmIDEpID8gJzEnIDogJzAnLCBuID4+PSAxOwogIHN0ZDo6cmV2ZXJzZShyZXQuYmVnaW4oKSwgcmV0LmVuZCgpKTsKICByZXR1cm4gcmV0Owp9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KaW5saW5lIHZvaWQgcHJpbnRsbihUIHZhbCkgewogIHN0ZDo6Y291dCA8PCB2YWwgPDwgJ1xuJzsKfQoKdGVtcGxhdGUgPGNsYXNzIFQ+CmlubGluZSB2b2lkIHByaW50bG4oY29uc3Qgc3RkOjp2ZWN0b3I8VD4mIHZlYykgewogIGludCBzeiA9IHZlYy5zaXplKCk7CiAgZm9yIChpbnQgaSA9IDA7IGkgPCBzejsgKytpKSBzdGQ6OmNvdXQgPDwgdmVjW2ldIDw8ICIgXG4iW2kgPT0gc3ogLSAxXTsKfQoKaW5saW5lIHZvaWQgWWVzKGJvb2wgY29uZCkgewogIHByaW50bG4oY29uZCA/ICJZZXMiIDogIk5vIik7Cn0KCmlubGluZSB2b2lkIFlFUyhib29sIGNvbmQpIHsKICBwcmludGxuKGNvbmQgPyAiWUVTIiA6ICJOTyIpOwp9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KdXNpbmcgYmluYXJ5X2hlYXAgPSBzdGQ6OnByaW9yaXR5X3F1ZXVlPFQsIHN0ZDo6dmVjdG9yPFQ+LCBzdGQ6OmdyZWF0ZXI8VD4+OwoKdGVtcGxhdGUgPGNsYXNzIFQ+CnN0ZDo6aXN0cmVhbSYgb3BlcmF0b3I+PihzdGQ6OmlzdHJlYW0mIGlzLCBzdGQ6OnZlY3RvcjxUPiYgdmVjKSB7CiAgZm9yIChUJiBlIDogdmVjKSBpcyA+PiBlOwogIHJldHVybiBpczsKfQoKdGVtcGxhdGUgPGNsYXNzIFQsIGNsYXNzIFU+CnN0ZDo6aXN0cmVhbSYgb3BlcmF0b3I+PihzdGQ6OmlzdHJlYW0mIGlzLCBzdGQ6OnBhaXI8VCwgVT4mIHApIHsKICByZXR1cm4gaXMgPj4gcC5maXJzdCA+PiBwLnNlY29uZDsKfQoKdGVtcGxhdGUgPGNsYXNzIFR1cGxlLCBzdGQ6OnNpemVfdC4uLiBJcz4Kdm9pZCB0dXBsZV9pbihzdGQ6OmlzdHJlYW0mIGlzLCBUdXBsZSYgdHAsIHN0ZDo6aW5kZXhfc2VxdWVuY2U8SXMuLi4+KSB7CiAgKChpcyA+PiBzdGQ6OmdldDxJcz4odHApKSwgLi4uKTsKfQoKdGVtcGxhdGUgPGNsYXNzLi4uIEFyZ3M+CnN0ZDo6aXN0cmVhbSYgb3BlcmF0b3I+PihzdGQ6OmlzdHJlYW0mIGlzLCBzdGQ6OnR1cGxlPEFyZ3MuLi4+JiB0cCkgewogIHR1cGxlX2luKGlzLCB0cCwgc3RkOjppbmRleF9zZXF1ZW5jZV9mb3I8QXJncy4uLj57fSk7CiAgcmV0dXJuIGlzOwp9CgoKdGVtcGxhdGUgPGNsYXNzIFQ+CmNsYXNzIGdyYXBoIHsKIHB1YmxpYzoKICBncmFwaChpbnQgbikgOiBuXyhuKSB7IGRhdGFfLnJlc2l6ZShuXyk7IH0KICBzdHJ1Y3QgZWRnZSB7CiAgICBpbnQgZnJvbSwgdG87CiAgICBUIGNvc3Q7CgogICAgZWRnZShpbnQgZnJvbV8sIGludCB0b18sIFQgY29zdF8pIDogZnJvbShmcm9tXyksIHRvKHRvXyksIGNvc3QoY29zdF8pIHt9CiAgfTsKICBpbnQgbl87CiAgc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8aW50Pj4gZGF0YV87CiAgc3RkOjp2ZWN0b3I8ZWRnZT4gZWRnZXNfOwoKICB2aXJ0dWFsIHZvaWQgYWRkKGludCBmcm9tLCBpbnQgdG8sIFQgY29zdCkgPSAwOwp9OwoKdGVtcGxhdGUgPGNsYXNzIFQ+CmNsYXNzIGZvcmVzdCA6IHB1YmxpYyBncmFwaDxUPiB7CiBwdWJsaWM6CiAgdXNpbmcgZ3JhcGg8VD46Om5fOwogIHVzaW5nIGdyYXBoPFQ+OjpkYXRhXzsKICB1c2luZyBncmFwaDxUPjo6ZWRnZXNfOwoKICBmb3Jlc3QoaW50IG4pIDogZ3JhcGg8VD4obikge30KCiAgdm9pZCBhZGQoaW50IGZyb20sIGludCB0bywgVCBjb3N0ID0gMSkgewogICAgYXNzZXJ0KDAgPD0gZnJvbSAmJiBmcm9tIDwgbl8gJiYgMCA8PSB0byAmJiB0byA8IG5fKTsKICAgIGludCBpZCA9IGVkZ2VzXy5zaXplKCk7CiAgICBhc3NlcnQoaWQgPCBuXyAtIDEpOwogICAgZGF0YV9bZnJvbV0uZW1wbGFjZV9iYWNrKGlkKTsKICAgIGRhdGFfW3RvXS5lbXBsYWNlX2JhY2soaWQpOwogICAgZWRnZXNfLmVtcGxhY2VfYmFjayhmcm9tLCB0bywgY29zdCk7CiAgfQp9OwoKdGVtcGxhdGUgPGNsYXNzIFQ+CmNsYXNzIGRpZ3JhcGggOiBwdWJsaWMgZ3JhcGg8VD4gewogcHVibGljOgogIHVzaW5nIGdyYXBoPFQ+OjpuXzsKICB1c2luZyBncmFwaDxUPjo6ZGF0YV87CiAgdXNpbmcgZ3JhcGg8VD46OmVkZ2VzXzsKCiAgZGlncmFwaChpbnQgbikgOiBncmFwaDxUPihuKSB7fQoKICB2b2lkIGFkZChpbnQgZnJvbSwgaW50IHRvLCBUIGNvc3QgPSAxKSB7CiAgICBhc3NlcnQoMCA8PSBmcm9tICYmIGZyb20gPCBuXyAmJiAwIDw9IHRvICYmIHRvIDwgbl8pOwogICAgaW50IGlkID0gZWRnZXNfLnNpemUoKTsKICAgIGRhdGFfW2Zyb21dLmVtcGxhY2VfYmFjayhpZCk7CiAgICBlZGdlc18uZW1wbGFjZV9iYWNrKGZyb20sIHRvLCBjb3N0KTsKICB9CgogIGRpZ3JhcGg8VD4gcmV2ZXJzZSgpIGNvbnN0IHsKICAgIGRpZ3JhcGg8VD4gcmV2KG5fKTsKICAgIGZvciAoY29uc3QgYXV0byYgW2Zyb20sIHRvLCBjb3N0XSA6IGVkZ2VzXykgewogICAgICByZXYuYWRkKHRvLCBmcm9tLCBjb3N0KTsKICAgIH0KICAgIHJldHVybiByZXY7CiAgfQp9OwoKdGVtcGxhdGUgPGNsYXNzIFQ+CmNsYXNzIHVuZGlncmFwaCA6IHB1YmxpYyBncmFwaDxUPiB7CiBwdWJsaWM6CiAgdXNpbmcgZ3JhcGg8VD46Om5fOwogIHVzaW5nIGdyYXBoPFQ+OjpkYXRhXzsKICB1c2luZyBncmFwaDxUPjo6ZWRnZXNfOwoKICB1bmRpZ3JhcGgoaW50IG4pIDogZ3JhcGg8VD4obikge30KCiAgdm9pZCBhZGQoaW50IGZyb20sIGludCB0bywgVCBjb3N0ID0gMSkgewogICAgYXNzZXJ0KDAgPD0gZnJvbSAmJiBmcm9tIDwgbl8gJiYgMCA8PSB0byAmJiB0byA8IG5fKTsKICAgIGludCBpZCA9IGVkZ2VzXy5zaXplKCk7CiAgICBkYXRhX1tmcm9tXS5lbXBsYWNlX2JhY2soaWQpOwogICAgZGF0YV9bdG9dLmVtcGxhY2VfYmFjayhpZCk7CiAgICBlZGdlc18uZW1wbGFjZV9iYWNrKGZyb20sIHRvLCBjb3N0KTsKICB9Cn07CgoKdGVtcGxhdGUgPGNsYXNzIFQ+CnN0ZDo6dmVjdG9yPFQ+IGRpamtzdHJhKGNvbnN0IGdyYXBoPFQ+JiBnLCBpbnQgcykgewogIGFzc2VydCgwIDw9IHMgJiYgcyA8IGcubl8pOwogIHN0ZDo6dmVjdG9yPFQ+IGRpc3QoZy5uXywgc3RkOjpudW1lcmljX2xpbWl0czxUPjo6bWF4KCkpOwogIHN0cnVjdCBQYWlyIHsKICAgIFQgZDsKICAgIGludCB2OwogICAgUGFpcihUIGRfLCBpbnQgdl8pIDogZChkXyksIHYodl8pIHt9CiAgICBib29sIG9wZXJhdG9yPChjb25zdCBQYWlyJiByaHMpIGNvbnN0IHsKICAgICAgcmV0dXJuIGQgPiByaHMuZDsKICAgIH0KICB9OwogIC8vc3RkOjpwcmlvcml0eV9xdWV1ZTxQYWlyLCBzdGQ6OnZlY3RvcjxQYWlyPiwgc3RkOjpncmVhdGVyPFBhaXI+PiBwcTsKICBzdGQ6OnByaW9yaXR5X3F1ZXVlPFBhaXI+IHBxOwogIGRpc3Rbc10gPSAwOwogIHBxLmVtcGxhY2UoMCwgcyk7CiAgd2hpbGUgKCFwcS5lbXB0eSgpKSB7CiAgICBhdXRvIFtkLCB2XSA9IHBxLnRvcCgpOwogICAgcHEucG9wKCk7CiAgICBpZiAoZGlzdFt2XSA8IGQpIGNvbnRpbnVlOwogICAgZm9yIChpbnQgaWQgOiBnLmRhdGFfW3ZdKSB7CiAgICAgIGNvbnN0IGF1dG8mIFtmcm9tLCB0bywgY29zdF0gPSBnLmVkZ2VzX1tpZF07CiAgICAgIGludCBueHQgPSBmcm9tIF4gdG8gXiB2OwogICAgICBpZiAoZGlzdFtueHRdID4gZGlzdFt2XSArIGNvc3QpIHsKICAgICAgICBkaXN0W254dF0gPSBkaXN0W3ZdICsgY29zdDsKICAgICAgICBwcS5lbXBsYWNlKGRpc3Rbbnh0XSwgbnh0KTsKICAgICAgfQogICAgfQogIH0KICByZXR1cm4gZGlzdDsKfQoKZGlncmFwaDxpbnQ+IGdyaWRfdG9fZGlncmFwaChjb25zdCBzdGQ6OnZlY3RvcjxzdGQ6OnN0cmluZz4mIHN2KSB7CiAgaW50IGggPSBzdi5zaXplKCksIHcgPSBzdlswXS5zaXplKCk7CiAgZGlncmFwaDxpbnQ+IGcoaCAqIHcpOwogIGNvbnN0ZXhwciBpbnQgZHhbNF0gPSB7MSwgMCwgLTEsIDB9LCBkeVs0XSA9IHswLCAxLCAwLCAtMX07CiAgYXV0byBPdXQgPSBbJl0oaW50IHgsIGludCB5KSB7IHJldHVybiAoeCA8IDAgfHwgeCA+PSBoIHx8IHkgPCAwIHx8IHkgPj0gdyk7IH07CiAgYXV0byBDb21wcmVzcyA9IFsmXShpbnQgeCwgaW50IHkpIHsgcmV0dXJuIHggKiB3ICsgeTsgfTsKICBmb3IgKGludCBpID0gMDsgaSA8IGg7ICsraSkgewogICAgZm9yIChpbnQgaiA9IDA7IGogPCB3OyArK2opIHsKICAgICAgZm9yIChpbnQgayA9IDA7IGsgPCA0OyArK2spIHsKICAgICAgICBpbnQgbnggPSBpICsgZHhba10sIG55ID0gaiArIGR5W2tdOwogICAgICAgIGlmIChPdXQobngsIG55KSkgY29udGludWU7CiAgICAgICAgaWYgKHN2W2ldW2pdID09ICcuJyAmJiBzdltueF1bbnldID09ICcuJykgewogICAgICAgICAgZy5hZGQoQ29tcHJlc3MoaSwgaiksIENvbXByZXNzKG54LCBueSksIDApOwogICAgICAgIH0KICAgICAgfQogICAgICBmb3IgKGludCBrID0gLTI7IGsgPD0gMjsgKytrKSB7CiAgICAgICAgZm9yIChpbnQgbCA9IC0yOyBsIDw9IDI7ICsrbCkgewogICAgICAgICAgaW50IG54ID0gaSArIGssIG55ID0gaiArIGw7CiAgICAgICAgICBpZiAoT3V0KG54LCBueSkpIGNvbnRpbnVlOwogICAgICAgICAgaWYgKGFicyhrKSArIGFicyhsKSA9PSAxKSBjb250aW51ZTsKICAgICAgICAgIGlmIChzdltpXVtqXSA9PSAnLicgJiYgc3ZbbnhdW255XSA9PSAnLicpIHsKICAgICAgICAgICAgZy5hZGQoQ29tcHJlc3MoaSwgaiksIENvbXByZXNzKG54LCBueSksIDEpOwogICAgICAgICAgfQogICAgICAgIH0KICAgICAgfQogICAgfQogIH0KICByZXR1cm4gZzsKfQoKCmludCBtYWluKCkgewogIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogIGNpbi50aWUobnVsbHB0cik7CgogIGludCBoLCB3OyBjaW4gPj4gaCA+PiB3OwogIGludCBjaCwgY3c7IGNpbiA+PiBjaCA+PiBjdzsgLS1jaDsgLS1jdzsKICBpbnQgZGgsIGR3OyBjaW4gPj4gZGggPj4gZHc7ICAtLWRoOyAtLWR3OwogIHZlY3RvcjxzdHJpbmc+IHMoaCk7IGNpbiA+PiBzOwogIGRpZ3JhcGg8aW50PiBnID0gZ3JpZF90b19kaWdyYXBoKHMpOwogCiAgdmVjdG9yIGRpc3QgPSBkaWprc3RyYShnLCBjaCAqIHcgKyBjdyk7CiAKICBpbnQgYW5zID0gZGlzdFtkaCAqIHcgKyBkd107CiAgaWYgKGFucyA9PSBudW1lcmljX2xpbWl0czxpbnQ+OjptYXgoKSkgYW5zID0gLTE7CiAgY291dCA8PCBhbnMgPDwgZW5kbDsKCiAgcmV0dXJuIDA7Cn0KIiIiCgp3aXRoIG9wZW4oJ3NvbC5jcHAnLCAndycpIGFzIGY6CiAgICBmLndyaXRlKGNvZGUpCgpzdWJwcm9jZXNzLlBvcGVuKFsnZysrJywgJy1zdGQ9YysrMTcnLCAnLU8yJywgJ3NvbC5jcHAnXSkuY29tbXVuaWNhdGUoKQpzdWJwcm9jZXNzLlBvcGVuKFsnLi9hLm91dCddLCBzdGRpbj1zeXMuc3RkaW4sIHN0ZG91dD1zeXMuc3Rkb3V0KS5jb21tdW5pY2F0ZSgp'))

Solution (Python):
from collections import deque

H, W = map(int, input().split())
cy, cx = map(int, input().split())
sy, sx = map(int, input().split())
tiles = [list(input()) for _ in range(H)]


INF = 10**4
arrived = [[INF for _ in range(W)] for __ in range(H)]
paths = deque()
warps = deque()
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
moves = [-2, -1, 0, 1, 2]
arrived[cy-1][cx-1] = 0
paths.append([cx-1, cy-1])
count = 0


while(len(paths) > 0):
  while(len(paths) > 0):
    nx, ny = paths.popleft()
    for i in range(4):
      if 0 <= nx+dx[i] < W and 0 <= ny+dy[i] < H and arrived[ny+dy[i]][nx+dx[i]] > count and tiles[ny+dy[i]][nx+dx[i]] == '.':
        paths.append([nx+dx[i], ny+dy[i]])
        arrived[ny+dy[i]][nx+dx[i]] = count
    for x in moves:
      for y in moves:
        if 0 <= nx+x < W and 0 <= ny+y < H and arrived[ny+y][nx+x] == INF and tiles[ny+y][nx+x] == '.':
          warps.append([nx+x, ny+y])
  count += 1
  while(len(warps) > 0):
    nx, ny = warps.popleft()
    if arrived[ny][nx] == INF:
      arrived[ny][nx] = count
      paths.append([nx, ny])

if arrived[sy-1][sx-1] != INF:
  print(arrived[sy-1][sx-1])
else:
  print(-1)

Solution (Python):
H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

INF = 10**9
dst = [[INF]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()
    for dh in range(-2, 3):
        for dw in range(-2, 3): 
            nh = h + dh; nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                f = dh*dh + dw*dw 
                if f == 1 and dst[nh][nw] > dst[h][w]:
                    dst[nh][nw] = dst[h][w]
                    dq.appendleft((nh, nw))
                elif f > 1 and dst[nh][nw] > dst[h][w] + 1:
                    dst[nh][nw] = dst[h][w] + 1
                    dq.append((nh, nw))

print(-1 if dst[eh][ew]==INF else dst[eh][ew])

Solution (Python):
H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

INF = 10**9
dst = [[INF]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for dh in range(-2, 3):
        for dw in range(-2, 3): 
            nh = h + dh; nw = w + dw
            if dh*dh + dw*dw == 1:
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and dst[h][w] < dst[nh][nw]:
                    dst[nh][nw] = dst[h][w]
                    dq.appendleft((nh, nw))
            elif dh*dh + dw*dw > 1:
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and dst[h][w] + 1 < dst[nh][nw]:
                    dst[nh][nw] = dst[h][w] + 1
                    dq.append((nh, nw))

print(-1 if dst[eh][ew]==INF else dst[eh][ew])

Solution (Python):
H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '
        dst[h][w] = d
        for dh in range(-2, 3):
            for dw in range(-2, 3): 
                if dh*dh + dw*dw == 1: dq.appendleft((h + dh, w + dw, d))
                elif dh*dh + dw*dw > 1: dq.append((h + dh, w + dw, d+1))

print(dst[eh][ew])

Solution (Python):
H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '
        dst[h][w] = d
        for dh in range(-2, 3):
            for dw in range(-2, 3): 
                if dh*dh + dw*dw < 1: continue
                if dh*dh + dw*dw > 1: dq.append((h + dh, w + dw, d+1))
                else: dq.appendleft((h + dh, w + dw, d))

print(dst[eh][ew])

Solution (Python):
h,w = map(int, input().split())

sy, sx = map(int, input().split())
sy -= 1
sx -= 1
gy, gx = map(int, input().split())
gy -= 1
gx -= 1

s = [[""] for _ in range(h)]
for i in range(h):
    s[i] = input()

from collections import deque
d = deque()

visited = [[False]*w for _ in range(h)]

d.append([sy,sx,0])

while len(d) > 0:
    y,x,c = d.popleft()
    
    if visited[y][x] is True:
        continue
    else:
        visited[y][x] = True
    
    if gy == y and gx == x:
        print(c)
        exit(0)

    dxy = [[1,0], [-1, 0], [0, 1], [0, -1]]
    for dx, dy in dxy:
        nx = dx + x
        ny = dy + y
        if nx < 0 or nx >= w or ny < 0 or ny >= h:
            continue
        if s[ny][nx] == "
            continue
        if visited[ny][nx] is True:
            continue
        d.appendleft([ny, nx, c])

    for dy in range(-2, 3):
        for dx in range(-2, 3):
            nx = dx + x
            ny = dy + y
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue
            if s[ny][nx] == "
                continue
            if visited[ny][nx] is True:
                continue
            d.append([ny, nx, c+1])

print(-1)

Solution (Python):
from heapq import heappush,heappop,heapify
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found

mo=10**9+7
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
import sys
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

inf=1<<20
def dijkstra(edge,st):
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    q=[(0,st)]
    heapify(q)
    v=[False]*n
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                heappush(q,(alt,dst))
    return d


show_flg=False
show_flg=True

ans=0

for _ in range(1):
    h,w=LI()
    sh,sw=LI()
    gh,gw=LI()
    
    w+=2
    m=[1]*w
    for i in range(h):
        s=input()
        m+=[1]+[i=='
    m+=[1]*w
    h+=2
    n=h*w
    v=[-1]*w*h
    
    
    nbw=[-2*w+1,-2*w+2,-w+1,-w+2,2,2*w+1,2*w+2,w+1,w+2,+2*w,-2*w,-2*w-1,-2*w-2,-w-1,-w-2,-2,2*w-1,2*w-2,w-1,w-2]
    nbw=[2,2*w+1,2*w+2,w+1,w+2,+2*w,2*w-1,2*w-2,w-1,w-2]
    nb=[1,-1,w,-w]
    nb=[1,w]
    d=[-1]*n
    g=[[]for i in range(n)]
    for i in range(n):
        if m[i]==1:
          continue
        for di in nbw:
            nx=i+di
            if 0<=nx<n and m[nx]!=1:
                g[i]+=(nx,1),
                g[nx]+=(i,1),
        for di in nb:
            nx=i+di
            if 0<=nx<n and m[nx]!=1:
                g[i]+=(nx,0),
                g[nx]+=(i,0),
                
    d=dijkstra(g,sh*w+sw)
    ans=d[gh*w+gw]
    if ans==inf:
        ans=-1
    print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
H,W=map(int,input().split())
cx,cy=map(lambda x: int(x)+1,input().split())
dx,dy=map(lambda x: int(x)+1,input().split())
S=["
l=[[-2]*(W+4) for i in range(H+4)]
for i in range(2,H+2):
    for j in range(2,W+2):
        if S[i][j]==".":
            l[i][j]=-1
l[cx][cy]=0
b=[(cx,cy)]
bb=[(cx,cy)]
t=0
while bb:
    while b:
        a=[]
        for i in b:
            if l[i[0]+1][i[1]]==-1:
                l[i[0]+1][i[1]]=t
                a.append((i[0]+1,i[1]))
            if l[i[0]-1][i[1]]==-1:
                l[i[0]-1][i[1]]=t
                a.append((i[0]-1,i[1]))
            if l[i[0]][i[1]+1]==-1:
                l[i[0]][i[1]+1]=t
                a.append((i[0],i[1]+1))
            if l[i[0]][i[1]-1]==-1:
                l[i[0]][i[1]-1]=t
                a.append((i[0],i[1]-1))
        bb+=a
        b=a
    aa=[]
    t+=1
    b=[]
    for i in bb:
        for j in range(-2,3):
            for k in range(-2,3):
                if l[i[0]+j][i[1]+k]==-1:
                    l[i[0]+j][i[1]+k]=t
                    aa.append((i[0]+j,i[1]+k))
                    b.append((i[0]+j,i[1]+k))
    if l[dx][dy]>=0:
        break
    bb=aa
print(l[dx][dy])

Solution (Python):





"""
"""

from collections import defaultdict
import bisect
from itertools import product
from collections import deque

import sys
input = sys.stdin.readline

def solve(h,w,ch,cw,dh,dw,s):
    d = [[10**7]*w for _ in range(h)]
    d[ch][cw] = 0
    dis0 = [(1,0),(0,1),(-1,0),(0,-1)]
    dis1 = [(i,j) for i,j in product(range(-2,3),range(-2,3)) if 1 < abs(i)+abs(j)]
    Q = deque([(ch,cw)])
    ans = -1
    while Q:
        pos1 = Q.pop()
        i, j = pos1
        if i == dh and j==dw:
            ans = d[dh][dw]
            break
        for pos2 in [(i+a,j+b) for a,b in dis0 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            alt = d[i][j] 
            if d[k][l] > alt:
                d[k][l] = alt
                Q.append((k,l))
        for pos2 in [(i+a,j+b) for a,b in dis1 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            alt = d[i][j]+1
            if d[k][l] > alt:
                d[k][l] = alt
                Q.appendleft((k,l))
    print(ans)



def main():
    h, w = list(map(int,input().split()))
    ch, cw = list(map(int,input().split()))
    dh, dw = list(map(int,input().split()))
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    s = []
    for _ in range(h):
        s.append(list(input().rstrip()))
    solve(h,w,ch,cw,dh,dw,s)


if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch - 1, cw - 1, dh - 1, dw - 1
S = [input() for _ in range(H)]

from collections import deque

def is_valid(h, w):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        return True
    else:
        return False

Dh = (1, 0, -1, 0)
Dw = (0, 1, 0, -1)

INF = float('inf')
dist = [[INF] * W for _ in range(H)]
dist[ch][cw] = 0
q = deque([(ch, cw)])

while q:
    ph, pw = q.popleft()
    for k in range(4):
        nh, nw = ph + Dh[k], pw + Dw[k]
        if is_valid(nh, nw):
            if dist[nh][nw] > dist[ph][pw]:
                dist[nh][nw] = dist[ph][pw]
                q.appendleft((nh, nw))
    for nh in range(ph - 2, ph + 3):
        for nw in range(pw - 2, pw + 3):
            if is_valid(nh, nw):
                if dist[nh][nw] > dist[ph][pw] + 1:
                   dist[nh][nw] = dist[ph][pw] + 1
                   q.append((nh, nw))

print(-1) if dist[dh][dw] == INF else print(dist[dh][dw])

Solution (Python):
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()

H, W = map(int, input().split())

ch, cw = map(int, input().split())
ch -= 1
cw -= 1
dh, dw = map(int, input().split())
dh -= 1
dw -= 1

maze = []
for i in range(H):
    a = list(input())
    maze.append(a)

queue = deque([(ch, cw, 0)])

dist = [[float("inf") for _ in range(W)] for _ in range(H)]
dist[ch][cw] = 0

while queue:
    y, x, cnt= queue.popleft()

    for a, b in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y+a, x+b
        if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] != '
            if dist[new_y][new_x] == float("inf") or dist[new_y][new_x] > cnt:
                queue.appendleft((new_y, new_x, cnt))
                dist[new_y][new_x] = cnt

    for a in range(-2, 3):
        for b in range(-2, 3):
            new_y, new_x = y + a, x + b
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] != '
                if dist[new_y][new_x] == float("inf") or dist[new_y][new_x] > cnt + 1:
                    queue.append((new_y, new_x, cnt+1))
                    dist[new_y][new_x] = cnt + 1

print(-1 if dist[dh][dw] == float("inf") else dist[dh][dw])

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math


rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	rows, cols = rli()
	r0, c0 = rli(); r0 -= 1; c0 -= 1;
	r1, c1 = rli(); r1 -= 1; c1 -= 1;
	G = []
	for _ in range(rows):
		row = []
		for c in rll()[0]:
			if c == "
				row.append(1)
			else:
				row.append(0)
		G.append(row)

	inside = lambda r, c: r>=0 and c>=0 and r<rows and c<cols	
	seen = [0 for _ in range(rows*cols+10)]
	Q = deque() 
	Q.append((0, r0, c0))
	ans = INF
	while Q:
		magics, r, c = Q.pop()
		val = r*cols + c 
		if seen[val]: continue
		seen[val] = True
		if r == r1 and c == c1:
			ans = magics 
			break
		for dr in range(-2, 3):
			for dc in range(-2, 3):
				nr, nc = r + dr, c + dc 
				if not inside(nr, nc) or seen[cols*nr + nc] or G[nr][nc] == 1: continue
				if abs(dr) + abs(dc) > 1:
					Q.appendleft((magics+1, nr, nc))
				else:
					Q.append((magics, nr, nc))
	print(ans if ans < INF else -1)
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
from collections import deque

def solve():
    H,W = map(int,input().split())
    C = list(map(int,input().split()))
    D = list(map(int,input().split()))

    S = ["
    for i in range(2):
        S.insert(0,"
        S.append("

    INF = float("inf")
    cost = [[INF for _ in range(W+4)] for _ in range(H+4)]
    cost0 = deque()
    ans = -1

    cost0.append((C[0]+1, C[1]+1, 0))
    cost[C[0]+1][C[1]+1] = 0

    move = [(1,0), (0,1), (-1,0), (0,-1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)]+move]

    cost1 = deque()

    while cost0:
        h,w,c = cost0.popleft()
        cost1.append((h,w,c))

        for i, j in move:
            dh = h+i
            dw = w+j
            if S[dh][dw] == "." and c < cost[dh][dw]:
                cost[dh][dw] = c
                cost0.appendleft((dh, dw, cost[dh][dw]))
        
        if len(cost0) == 0:
            while cost1:
                h, w, c = cost1.popleft()
                for i, j in warp:
                    dh = h+i
                    dw = w+j
                    if S[dh][dw] == "." and c+1 < cost[dh][dw]:
                        cost[dh][dw] = c+1
                        cost0.append((dh,dw, cost[dh][dw]))
        
        if cost[D[0]+1][D[1]+1] != INF:
            ans = cost[D[0]+1][D[1]+1]

    print(ans)

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from collections import deque

h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch,cw=ch-1,cw-1
dh,dw=map(int,input().split())
dh,dw=dh-1,dw-1
s=[[*next(sys.stdin)] for _ in range(h)]

c=-1
for i in range(h):
    for j in range(w):
        if s[i][j]!='.':
            continue
        c+=1
        stk=[(i,j)]
        while stk:
            ii,jj=stk.pop()
            s[ii][jj]=c
            for di,dj in (-1,0),(0,1),(1,0),(0,-1):
                ni,nj=ii+di,jj+dj
                if not (0<=ni<h and 0<=nj<w):
                    continue
                if s[ni][nj]!='.':
                    continue
                stk.append((ni,nj))

n=c+1
cc=dc=-1
dirs=[-2,-1,0,1,2]
adj=[{*()} for _ in range(n)]
for i in range(h):
    for j in range(w):
        u=s[i][j]
        if u=='
            continue
        if i==ch and j==cw:
            cc=u
        elif i==dh and j==dw:
            dc=u
        for di in dirs:
            for dj in dirs:
                if di==dj==0:
                    continue
                ni,nj=i+di,j+dj
                if not (0<=ni<h and 0<=nj<w):
                    continue
                v=s[ni][nj]
                if v=='
                    continue
                if u!=v:
                    adj[u].add(v)
                    adj[v].add(u)

que=deque()                
que.append(cc)
vis={cc}
m=-1
while que:
    m+=1
    for _ in range(len(que)):
        u=que.popleft()
        if u==dc:
            print(m)
            exit()
        for v in adj[u]:
            if v in vis:
                continue
            vis.add(v)
            que.append(v)

print(-1)

Solution (Python):
from queue import deque
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
DH,DW = DH-1,DW-1
S=[]
for i in range(H):
    S.append(list(map(lambda x:0 if x=='.' else -1, input().strip())))

def walk(h,w,n):
    r = []
    q = deque([(h,w)])
    while q:
        x = q.pop()
        r.append(x)
        h,w = x
        if h == DH and w == DW:
            print(n-1)
            exit()
        if h > 0 and S[h-1][w] == 0:
            S[h-1][w] = n
            q.append((h-1,w))
        if h < H-1 and S[h+1][w] == 0:
            S[h+1][w] = n
            q.append((h+1,w))
        if w > 0 and S[h][w-1] == 0:
            S[h][w-1] = n
            q.append((h,w-1))
        if w < W-1 and S[h][w+1] == 0:
            S[h][w+1] = n
            q.append((h,w+1))
    return r

warp = 1
q = deque([(CH-1,CW-1)])
while len(q) > 0:
    n = []
    while len(q) > 0:
        h,w = q.pop()
        n+=walk(h,w,warp)
    warp += 1
    if len(n) == 0:
        break
    for h,w in n:
        for ah in range(max(0,h-2),min(H,h+3)):
            for aw in range(max(0,w-2),min(W,w+3)):
                if ah == DH and aw == DW:
                    print(warp-1)
                    exit()
                if S[ah][aw] == 0:
                    S[ah][aw] = warp
                    q.append((ah,aw))

print(-1)

Solution (Python):

from collections import 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

maze = [input() for _ in range(H)]

INF = 10 ** 12

score = [[INF] * W for _ in range(H)]

score[Ch][Cw] = 0

candidates = deque()
candidates.append((Ch, Cw))

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

while candidates:
    h, w = candidates.popleft()
    
    for dh, dw in walk:
        y = h + dh
        x = w + dw
        s = score[h][w]
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue        
        if maze[y][x] == '.' and score[y][x] > s:
            score[y][x] = s
            candidates.appendleft((y, x))
    
    for dh, dw in warp:
        y = h + dh
        x = w + dw
        s = score[h][w]
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue
        if maze[y][x] == '.' and score[y][x] > s + 1:
            score[y][x] = s + 1
            candidates.append((y, x))

if score[Dh][Dw] == INF:
    print(-1)
else:
    print (score[Dh][Dw])