{-# LANGUAGE BangPatterns        #-}
{-# LANGUAGE FlexibleContexts    #-}
{-# LANGUAGE MultiWayIf          #-}
{-# LANGUAGE RankNTypes          #-}
{-# LANGUAGE ScopedTypeVariables #-}
import           Control.Monad
import           Control.Monad.ST
import           Control.Monad.State
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.List
import           Data.Sequence               (Seq ((:<|), (:|>)), ViewL ((:<)),
                                              ViewR ((:>)), viewl, viewr, (<|),
                                              (><), (|>))
import qualified Data.Sequence               as Seq
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import           Debug.Trace

main :: IO ()
main = do
  [h,w] <- readLnAsListWith unconsInt
  [cx,cy] <- readLnAsListWith unconsInt
  [dx,dy] <- readLnAsListWith unconsInt
  sgrid <- readLnAs2DUVecWith unconsChar h w :: IO (VU.Vector Char)

  let ggrid = gridBfs (h,w) (cx-1,cy-1) (\g (i,j) -> g VU.! gridIndex w i j == '.') sgrid

  print $ ggrid VU.! gridIndex w (dx-1) (dy-1)

  return ()


type Grid a = VU.Vector a
type MGrid s = VUM.MVector s

gridBfs :: (Int,Int) -> (Int,Int) -> (Grid a -> (Int,Int) -> Bool) -> Grid a -> VU.Vector Int
gridBfs (h',w') (sh,sw) f g = VU.create $ do
  seen <- VUM.replicate (h'*w') False
  dist <- VUM.replicate (h'*w') (-1)

  VUM.write dist (ix (sh,sw)) 0
  let deque = Seq.empty |> ix (sh,sw)
  go dist seen deque

  return dist

  where go :: MGrid s Int -> MGrid s Bool -> Seq Int -> ST s ()
        go dist seen dq =
          case dq of
            Seq.Empty -> return ()
            _         -> do
              let (curr :< dq') = viewl dq
              s <- VUM.read seen curr
              if s then go dist seen dq' else do
                VUM.write seen curr True
                cost <- VUM.read dist curr

                candCost0 <- filterM (VUM.read dist >=> return . ((||) <$> (==(-1)) <*> (>cost))) $ neighbour4 curr
                forM_ candCost0 $ \next -> VUM.write dist next cost

                candCost1 <- filterM (VUM.read dist >=> return . (==(-1))) $ neighbour25 curr
                forM_ candCost1 $ \next -> VUM.write dist next (cost+1)

                let nextDq = foldr (<|) (foldl' (|>) dq' candCost1) candCost0
                go dist seen nextDq

        neighbour4 :: Int -> [Int]
        neighbour4 hw = let (h,w) = xi hw
                        in map ix $ filter inGrid [(h+x,w+y) | (x,y) <- [(-1,0),(1,0),(0,-1),(0,1)]]

        neighbour25 :: Int -> [Int]
        neighbour25 hw = let (h,w) = xi hw
                         in map ix $ filter inGrid [(h+x,w+y) | x <- [-2..2], y <- [-2..2], (x,y) /= (0,0)]

        inGrid :: (Int,Int) -> Bool
        inGrid (h,w) = h>=0 && h<h' && w>=0 && w<w' && g `f` (h,w)

        ix :: (Int,Int) -> Int
        ix (i,j) = gridIndex w' i j

        xi :: Int -> (Int,Int)
        xi ij = (ij`div`w',ij`mod`w')



-- converter
unconsChar :: StateT BS.ByteString Maybe Char
unconsChar = StateT BS.uncons

unconsInt :: StateT BS.ByteString Maybe Int
unconsInt = StateT $ BS.readInt . BS.dropWhile isSpace

readLnAsListWith :: StateT BS.ByteString Maybe a -> IO [a]
readLnAsListWith !st = unfoldr (runStateT st) <$> BS.getLine

-- for unboxed vector
readLnAs2DUVecWith :: VU.Unbox a => StateT BS.ByteString Maybe a -> Int -> Int -> IO (VU.Vector a)
readLnAs2DUVecWith !st !n !m = VU.unfoldrN (n * m) (runStateT st) . BS.concat <$> replicateM n BS.getLine

-- indexing
-- i: height (row)
-- j: width (column)
gridIndex :: Int -> Int -> Int -> Int
gridIndex w i j = i * w + j


Measured memory_bytes: 29476