Submission #420581

---

Source Code Expand

import qualified Data.Vector as V
import qualified Data.Set as S
main =  mapM_ (putStrLn . (\x->if x then "Yes" else "No") . solve) . analyze . lines =<< getContents
analyze (hw:xs) = (h,w,y): analyze ys where
  [h,w] = map read . words $ hw
  (y,ys) = splitAt h xs
analyze _ = []
solve (h,w,cs) = fst $ dfs S.empty si sj where
  (si,sj) = fs 0 0
  b = V.fromList $ map V.fromList cs
  fs i j
    | b V.! i V.! j == 's' = (i,j)
    | otherwise = fs (i+(j+1)`div`w) ((j+1)`mod`w)
  dfs s i j
    | i<0 || h<=i || j<0 || w<=j = (False,s)
    | c=='#' = (False,s)
    | c=='g' = (True,s)
    | S.member (i,j) s = (False,s)
    | otherwise = foldr f (False,S.insert (i,j) s) [(0,1),(0,-1),(1,0),(-1,0)]
    where
      c = b V.! i V.! j
      f (di,dj) (r,s) = (r || q, t) where (q,t) = dfs s (i+di) (j+dj)

Submission Info

Judge Result