{-# LANGUAGE BangPatterns        #-}
{-# LANGUAGE FlexibleContexts    #-}
{-# LANGUAGE MultiWayIf          #-}
{-# LANGUAGE RankNTypes          #-}
{-# LANGUAGE ScopedTypeVariables #-}
import           Control.Monad
import           Control.Monad.ST
import           Control.Monad.State
import           Data.Array.IArray
import           Data.Array.ST
import           Data.Array.Unboxed
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

main :: IO ()
main = do
  [h,w] <- readLnAsListWith unconsInt
  [cx,cy] <- readLnAsListWith unconsInt
  [dx,dy] <- readLnAsListWith unconsInt
  sgrid <- readLnAs2DArrayWith unconsChar h w :: IO (UArray (Int,Int) Char)

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

  print $ ggrid ! (dx,dy)

  return ()


type Grid a = UArray (Int,Int) a
type MGrid s = STUArray s (Int,Int)


gridBfs :: (Int,Int) -> (Int,Int) -> (Grid a -> (Int,Int) -> Bool) -> Grid a -> UArray (Int,Int) Int
gridBfs (h',w') (sh,sw) f g = runSTUArray $ do
  seen <- newArray ((1,1),(h',w')) False
  dist <- newArray ((1,1),(h',w')) (-1)

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

  return dist

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

                let p0 = \x -> x==(-1) || x>cost
                    p1 = (==(-1))

                candCost0 <- filterM (readArray dist >=> return . p0) (neighbour4 curr)
                forM_ candCost0 $ \next -> writeArray dist next cost

                candCost1 <- filterM (readArray dist >=> return . p1) (neighbour25 curr)
                forM_ candCost1 $ \next -> writeArray dist next (cost+1)

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

        neighbour4 :: (Int,Int) -> [(Int,Int)]
        neighbour4 (h,w) = filter inGrid [(h+x,w+y) | (x,y) <- [(-1,0),(1,0),(0,-1),(0,1)]]

        neighbour25 :: (Int,Int) -> [(Int,Int)]
        neighbour25 (h,w) = filter inGrid [(h+x,w+y) | x <- [-2..2], y <- [-2..2], (x,y) /= (0,0)]

        inGrid :: (Int,Int) -> Bool
        inGrid (h,w) = h >= 1 && h <= h' && w >= 1 && w <= w' && not (g `f` (h,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

readLnAs2DArrayWith :: IArray a e => StateT BS.ByteString Maybe e -> Int -> Int -> IO (a (Int,Int) e)
readLnAs2DArrayWith !st !n !m = listArray ((1,1),(n,m)) . unfoldr (runStateT st) . BS.concat <$> replicateM n BS.getLine


Measured memory_bytes: 31592