module deque_mod
    use,intrinsic :: iso_fortran_env
    implicit none
    type deque
        integer(int32),pointer:: v(:)
        integer(int32):: l,r
        integer(int32):: lmax, rmax
    contains
        procedure:: append => dq_append
        procedure:: appendleft => dq_appendleft
        procedure:: pop => dq_pop
        procedure:: popleft => dq_popleft
        procedure:: right => dq_right
        procedure:: left => dq_left
        procedure:: remaining_elements => dq_remaining_elements
        procedure:: remain => dq_remain
    end type

    interface deque
        procedure:: dq_init
    end interface
contains
    function dq_init() result(dq)
        ! 初期化
        type(deque):: dq
        dq%r=0; dq%rmax=1
        dq%l=1; dq%lmax=-1
        allocate(dq%v(dq%lmax:dq%rmax))
    end function


    subroutine dq_append(dq,num)
        ! 右端に挿入
        class(deque):: dq
        integer(int32):: num
        if (dq%r+1 > dq%rmax) call dq_add_(dq)
        dq%r=dq%r+1
        dq%v(dq%r) = num
    end subroutine

    subroutine dq_appendleft(dq,num)
        ! 左端に挿入
        class(deque):: dq
        integer(int32):: num
        if (dq%l-1 < dq%lmax) call dq_add_(dq)
        dq%l=dq%l-1
        dq%v(dq%l) = num
    end subroutine

    subroutine dq_add_(dq)
        ! arrayの延長
        class(deque):: dq
        integer(int32):: l
        integer(int32),pointer:: tmp(:)
        l = size(dq%v)
        allocate(tmp(l))
        tmp(:) = dq%v(:)
        deallocate(dq%v)
        allocate(dq%v(3*dq%lmax:3*dq%rmax))
        dq%v(dq%lmax:dq%rmax) = tmp(:)
        dq%lmax = 3*dq%lmax
        dq%rmax = 3*dq%rmax
    end subroutine


    function dq_pop(dq) result(ret)
        ! 右端から取り出し
        class(deque):: dq
        integer(int32):: ret
        ret = dq%v(dq%r)
        dq%r=dq%r-1
    end function

    function dq_popleft(dq) result(ret)
        ! 左端から取り出し
        class(deque):: dq
        integer(int32):: ret
        ret = dq%v(dq%l)
        dq%l=dq%l+1
    end function


    function dq_right(dq) result(ret)
        ! 右端を確認
        class(deque):: dq
        integer(int32):: ret
        ret = dq%v(dq%r)
    end function

    function dq_left(dq) result(ret)
        ! 左端を確認
        class(deque):: dq
        integer(int32):: ret
        ret = dq%v(dq%l)
    end function

    function dq_remaining_elements(dq) result(ret)
        ! 残りの要素数
        class(deque):: dq
        integer(int32):: ret 
        ret = dq%r - dq%l + 1
    end function

    function dq_remain(dq) result(ret)
        ! 要素が残っているかどうか
        class(deque):: dq
        logical:: ret
        ret = dq%remaining_elements() > 0
    end function
end module

program main
    use,intrinsic :: iso_fortran_env
    use deque_mod
    implicit none
    integer(int32):: h,w,sx,sy,gx,gy,i,j,x,y,dx,dy,nx,ny
    integer(int32),allocatable:: nm(:,:)
    character(1),allocatable:: s(:,:)
    logical,allocatable:: passed(:,:)
    type(deque):: tx, ty, tx2,ty2

    tx = deque()
    ty = deque()
    tx2 = deque()
    ty2 = deque()
    read*, h,w
    read*, sy,sx
    read*, gy,gx

    allocate(nm(w,h), source=1000000000)
    allocate(s(w,h))
    allocate(passed(w,h),source=.false.)
    
    do y=1,h
        block; character(w):: inpt_s
            read*, inpt_s
            do x=1,w
                s(x,y) = inpt_s(x:x)
            end do
        end block
    end do

    call tx%append(sx)
    call ty%append(sy)
    nm(sx,sy) = 0

    do while(tx%remain())
        do while(tx%remain())
            x = tx%popleft()
            y = ty%popleft()
            ! print'(*(i0,1x))', x,y
            passed(x,y) = .true.
            call tx2%append(x)
            call ty2%append(y)
            ! do i=1,h
            !     print'(*(i0,1x))', nm(:,i)
            ! end do

            do dy = -1,1
                do dx = -1,1
                    if (dx==0 .and. dy==0) cycle
                    if (dx /= 0 .and. dy /= 0) cycle
                    nx = x+dx; ny = y+dy
                    if (.not. in_s(nx,ny)) cycle
                    if (s(nx,ny) == "#") cycle
                    if (nm(nx,ny) > nm(x,y)) then
                        ! print'(*(i0,1x))', nx,ny
                        nm(nx,ny) = nm(x,y)
                        call tx%append(nx)
                        call ty%append(ny)
                    end if
                end do
            end do
        end do

        do while(tx2%remain())
            x = tx2%popleft()
            y = ty2%popleft()
            do dy=-2,2
                do dx=-2,2
                    nx = dx+x; ny=dy+y
                    if (.not. in_s(nx,ny)) cycle
                    if (s(nx, ny) == "#") cycle
                    if (nm(nx,ny) > nm(x,y)+1) then
                        ! print'(*(i0,1x))', nx,ny
                        nm(nx,ny) = nm(x,y)+1
                        call tx%append(nx)
                        call ty%append(ny)
                    end if
                end do
            end do
        end do
    end do

    if (nm(gx,gy) == 1000000000) then
        print'(i0)', -1
        stop
    end if
    print'(i0)', nm(gx,gy)
contains
    function in_s(x,y) result(ret)
        integer(int32):: x,y
        logical:: ret

        ret = 1 <= x .and. x <= w
        ret = ret .and. (1 <= y .and. y <= h)
    end function
end program main

Measured memory_bytes: 30344