MODULE stackMod
      IMPLICIT NONE
!Module for STACK : Last in, First out
!reference : プログラミングコンテスト攻略のための
!             アルゴリズムとデータ構造

!2020/05/04 sizeを追加．精度をパラメータに変更．
!2020/07/06 if文からmodを使用するように変更。
!2020/07/07 binをallocatableに変更。コンパイルを楽にした。

      integer,parameter,private :: binSize = 10**5
      integer,parameter,private :: p = 8
      
      type intStack
        private
        !bin(0)は意味のある値を持たない
        integer(p),allocatable :: bin(:)
        integer(p) :: top = 0
        
        contains
        procedure,public,pass :: initialize => intStackInitialize
        procedure,public,pass :: isEmpty    => intStackIsEmpty
        procedure,public,pass :: isFull     => intStackIsFull
        procedure,public,pass :: push       => intStackPush
        procedure,public,pass :: pop        => intStackPop
        procedure,public,pass :: size       => intStackSize
      end type
      
      contains
!スタックを初期化、リセットする。初回は必ず呼んでほしい。
      subroutine intStackInitialize( s )
        implicit none
        class(intStack),intent(inout) :: s
        
        if( .not.allocated(s%bin) )then
          allocate( s%bin(0:binSize),source=0_p )
        end if
        
        s%top = 0
      end subroutine
      
      function intStackIsEmpty( s ) result( TorF )
        implicit none
        class(intStack),intent(in) :: s
        logical :: TorF
        
        TorF = s%top==0
      end function
      
      function intStackIsFull( s ) result( TorF )
        implicit none
        class(intStack),intent(in) :: s
        logical :: TorF
        
        TorF = s%top>=binSize
      end function
      
!スタックに値を入れる。
      subroutine intStackPush( s,x )
        implicit none
        class(intStack),intent(inout) :: s
        integer(p)     ,intent(in)    :: x
        
        if( s%isFull() )then
          print*,'Stack is full, Error!';stop
        end if
        
        s%top = s%top + 1
        s%bin(s%top) = x
      end subroutine
      
!スタックから値を得る。
      function intStackPop( s ) result( x )
        implicit none
        class(intStack),intent(inout) :: s
        integer(p) :: x
        
        if( s%isEmpty() )then
          print*,'Stack is empty, Error!';stop
        end if
        
        x = s%bin(s%top)
        s%top = s%top - 1
      end function
      
!スタックに入っている値の数を得る。
      function intStackSize( s ) result( x )
        implicit none
        class(intStack),intent(in) :: s
        integer(p) :: x
        
        x = s%top
      end function
      
      END MODULE stackMod

!!!!!  procedure list  !!!!!
! type(intStack) :: S
! S%push( int )
! S%size()
! int = S%pop()
! logical = S%isEmpty()
! logical = S%isFull()
! S%initialize()
! 
! 初回は必ずinitialize()を呼んでほしい!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


      PROGRAM piyo
      use stackMod
      IMPLICIT NONE
      INTEGER,PARAMETER :: p = 8
      type(intStack) :: wR,wC,jR,jC
      integer(p) :: h,w,i,j, start(2),d(2),numMagic,r,c,nr,nc
      integer(p) :: news1(4),news2(4)
      integer(p),allocatable :: s(:,:)
      character(10**3) :: ch
      
      call wr%initialize()
      call wc%initialize()
      call jr%initialize()
      call jc%initialize()
      
      read*,h,w
      allocate( s(h,w) )
      read*,start
      read*,d
      do i = 1,h
        read*,ch
        do j = 1,w
          if( ch(j:j)=='#' )then
            s(i,j) = -1
          else
            s(i,j) = 10**7
          end if
        end do
      end do
      
      
      news1 = [1,0,-1,0]
      news2 = [0,1,0,-1]
      
      numMagic = 0
      call wR%push(start(1))
      call wC%push(start(2))
      call jR%push(start(1))
      call jC%push(start(2))
      
      do while(.true.)
        do while(.true.)
          if( wR%isEmpty() ) exit
          r = wr%pop()
          c = wc%pop()
          call jr%push( r )
          call jc%push( c )
          do i = 1,4
            nr = r + news1(i)
            nc = c + news2(i)
            if( nr<1.or.h<nr.or.nc<1.or.w<nc ) cycle
            if( s(nr,nc)>numMagic )then
     !   print*,nr,nc
              s(nr,nc) = numMagic
              call wr%push( nr )
              call wc%push( nc )
              call jr%push( nr )
              call jc%push( nc )
            end if
          end do
        end do
        
 !       print*,'walking finish'
        numMagic = numMagic + 1
        do while(.true.)
          if( jr%isEmpty() ) exit
          
          
          r = jr%pop()
          c = jc%pop()
          do i = -2,2
            do j = -2,2
              if( i==0.and.j==0 )cycle
              nr = r + i
              nc = c + j
              if( nr<1.or.h<nr.or.nc<1.or.w<nc ) cycle
              if( s(nr,nc)>numMagic )then
     !     print*,nr,nc
                s(nr,nc) = numMagic
                call wr%push( nr )
                call wc%push( nc )
              end if
            end do
          end do
        end do
        
    !    print*,'jumping finish'
        
        if( wr%isEmpty() .and. jr%isEmpty() )then
          exit
        end if
      end do
      
      if( s(d(1),d(2))==10**7 )then
        print*,'-1'
      else
        print*,s(d(1),d(2))
      end if

      
      stop
      !debugg
      
      do i = 1,h
          print'(*(i8,x))',s(i,:)
      end do
      
      END PROGRAM

Measured memory_bytes: 13812