{-# LANGUAGE BangPatterns #-}
import Control.Exception (assert)
import Control.Monad
import Control.Monad.Primitive
import qualified Control.Monad.ST as ST
import qualified Data.Array.IO as IO
import qualified Data.Array.ST as ST
import qualified Data.Array.Unboxed as A
import Data.Bits
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.Foldable
import Data.List
import qualified Data.Map.Strict as Map
import Data.Maybe
import qualified Data.Sequence as Seq
import qualified Data.Set as Set
import qualified Data.Vector as VB
import qualified Data.Vector.Mutable as VBM
import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed.Base
import qualified Data.Vector.Unboxed.Mutable as VM
import Debug.Trace
readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine
inf :: Int
inf = 10^18
data IOUQueue a = IOUQueue { uq_size :: !Int
, uq_orig :: !Int
, uq_i :: !Int
, uq_j :: !Int
, uq_v :: VM.MVector (PrimState IO) a
}
newUDequeue :: (Unbox a) => Int -> Int -> IO (IOUQueue a)
newUDequeue sizel sizer = do let sz = sizel + sizer
v <- VM.new sz
return $ IOUQueue sz sizel sizel sizel v
newUQueue :: (Unbox a) => Int -> IO (IOUQueue a)
newUQueue sz = newUDequeue 0 sz
nullUQ :: (Unbox a) => IOUQueue a -> Bool
nullUQ uq@(IOUQueue _ _ i j _) = (i == j)
poplUQ :: (Unbox a) => IOUQueue a -> IO (IOUQueue a, a)
poplUQ uq@(IOUQueue sz o i j v) | i < j = do r <- VM.unsafeRead v i
return (uq{uq_i=i+1}, r)
| otherwise = error "poplUQ: empty queue"
popRUQ :: (Unbox a) => IOUQueue a -> IO (IOUQueue a, a)
popRUQ uq@(IOUQueue sz o i j v) | i < j = do r <- VM.unsafeRead v (j-1)
return (uq{uq_j=j-1}, r)
| otherwise = error "poprUQ: empty queue"
recenterUQ :: (Unbox a) => IOUQueue a -> IO (IOUQueue a)
recenterUQ uq@(IOUQueue sz o i j v)
| i == o = return uq
| i > o = do let dist = i - o
forM_ [i..(j-1)] $ \k -> do
t <- VM.unsafeRead v k
VM.unsafeWrite v (k-dist) t
return $ uq{uq_i=i-dist, uq_j=j-dist}
| otherwise = do let dist = o - j
forM_ [j-1,(j-2)..i] $ \k -> do
t <- VM.unsafeRead v k
VM.unsafeWrite v (k+dist) t
return $ uq{uq_i=i+dist, uq_j=j+dist}
pushListUQ :: (Unbox a) => IOUQueue a -> [a] -> IO (IOUQueue a)
pushListUQ uq [] = return uq
pushListUQ uq@(IOUQueue sz o i j v) (x:xs)
| j < sz = do VM.unsafeWrite v j x
pushListUQ uq{uq_j=j+1} xs
| i > o = do uq' <- recenterUQ uq
pushListUQ uq' (x:xs)
| otherwise = error "pushListUQ: overflow"
pushListWithDUQ :: (Unbox a, Unbox b) => IOUQueue (a, b) -> [a] -> b -> IO (IOUQueue (a, b))
pushListWithDUQ uq [] _ = return uq
pushListWithDUQ uq@(IOUQueue sz o i j v) (x:xs) d
| j < sz = do VM.unsafeWrite v j (x, d)
pushListWithDUQ uq{uq_j=j+1} xs d
| i > o = do uq' <- recenterUQ uq
pushListWithDUQ uq' (x:xs) d
| otherwise = error "pushListWithDUQ: overflow"
pushUQ :: (Unbox a) => IOUQueue a -> a -> IO (IOUQueue a)
pushUQ uq@(IOUQueue sz o i j v) x
| j < sz = do VM.unsafeWrite v j x
return $ uq{uq_j=j+1}
| i > o = do uq' <- recenterUQ uq
pushUQ uq' x
| otherwise = error "pushUQ: overflow"
pushLListUQ :: (Unbox a) => IOUQueue a -> [a] -> IO (IOUQueue a)
pushLListUQ uq [] = return uq
pushLListUQ uq@(IOUQueue sz o i j v) (x:xs)
| i > 0 = do VM.unsafeWrite v (i-1) x
pushLListUQ uq{uq_i=i-1} xs
| j < o = do uq' <- recenterUQ uq
pushLListUQ uq' (x:xs)
| otherwise = error "pushLListUQ: overflow"
pushLListWithDUQ :: (Unbox a, Unbox b) => IOUQueue (a, b) -> [a] -> b -> IO (IOUQueue (a, b))
pushLListWithDUQ uq [] _ = return uq
pushLListWithDUQ uq@(IOUQueue sz o i j v) (x:xs) d
| i > 0 = do VM.unsafeWrite v (i-1) (x, d)
pushLListWithDUQ uq{uq_i=i-1} xs d
| j < o = do uq' <- recenterUQ uq
pushLListWithDUQ uq' (x:xs) d
| otherwise = error "pushLListWithDUQ: overflow"
pushLUQ :: (Unbox a) => IOUQueue a -> a -> IO (IOUQueue a)
pushLUQ uq@(IOUQueue sz o i j v) x
| i > 0 = do VM.unsafeWrite v (i-1) x
return $ uq{uq_i=i-1}
| j < o = do uq' <- recenterUQ uq
pushLUQ uq' x
| otherwise = error "pushLUQ: overflow"
main = do
[h, w] <- getIntList
g <- VB.replicateM h BS.getLine
tps <- VBM.new (fromEnum 'z' - fromEnum 'a' + 1)
VBM.set tps ([] :: [(Int, Int)])
let getC y x | y >= 0 && y < h && x >= 0 && x < w = (g VB.! y) `BS.index` x
| otherwise = '#'
scanG :: Int -> Int -> (Int, Int) -> (Int, Int) -> IO ((Int, Int), (Int, Int))
scanG y x s g | y > h = return (s, g)
| x > w = scanG (y+1) 0 s g
| otherwise = do
let c = getC y x
case () of
() | c == 'S' -> scanG y (x+1) (y,x) g
| c == 'G' -> scanG y (x+1) s (y,x)
| c == '.' || c == '#' -> scanG y (x+1) s g
| otherwise -> do let j = fromEnum c - fromEnum 'a'
t <- VBM.unsafeRead tps j
VBM.unsafeWrite tps j ((y,x):t)
scanG y (x+1) s g
((sy,sx), (gy, gx)) <- scanG 0 0 (-1,-1) (-1,-1)
let nextPoss :: Int -> Int -> IO [(Int, Int)]
nextPoss y x = do let c = getC y x
ns = [(y', x')
| (y', x') <- [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]
, getC y' x' /= '#']
if (c >= 'a' && c <= 'z')
then do tp <- VBM.unsafeRead tps (fromEnum c - fromEnum 'a')
VBM.unsafeWrite tps (fromEnum c - fromEnum 'a') []
return $ ns ++ tp
else return ns
arr <- IO.newArray ((0,0),(h-1,w-1)) inf :: IO (IO.IOUArray (Int, Int) Int)
uq <- newUQueue 2000000
let bfs :: IOUQueue ((Int, Int), Int) -> IO ()
bfs uq | nullUQ uq = return ()
| otherwise = do (uq', ((y, x), d)) <- poplUQ uq
t <- IO.readArray arr (y, x)
if (d < t)
then do IO.writeArray arr (y, x) d
ns <- nextPoss y x
uq'' <- pushListWithDUQ uq' ns (d+1)
bfs uq''
else bfs uq'
uq1 <- pushUQ uq ((sy, sx), 0)
bfs uq1
dist <- IO.readArray arr (gy, gx)
print $ if dist == inf then (-1) else dist