import Data.Bool import Data.Char import Data.IntMap.Strict ((!)) import qualified Data.IntMap.Strict as M import qualified Data.Set as S import qualified Data.ByteString.Char8 as B type Vertex = Int type Cost = Int type Heap = S.Set (Cost, Vertex) nullq = S.null empty = S.empty push v c = S.insert (c,v) pop = S.deleteFindMax pos n x y = (n+1)*(x-1) + (y-1) north n p = p + (n+1) south n p = p - (n+1) east p = succ p west p = pred p inbound n p = p>=0 && p<=n*(n+1)-1 && mod p (n+1) /= n main = do [n,v,ox,oy] <- map read . words <$> getLine g <- B.filter (/= ' ') <$> B.getContents putStrLn (bool "NO" "YES" (oasys n v ox oy g)) oasys n v ox oy g = M.member pds im1 || ((M.member po im1) && (M.member pds im2)) where (im1,_) = until (nullq . snd) (dp n g) (im0,q0) (im2,_) = until (nullq . snd) (dp n g) (im0,q1) pdp = pos n 1 1 pds = pos n n n po = pos n oy ox im0 = M.empty q0 = push pdp v empty q1 = push po ((im1!po)*2) empty dp n g (im,q) | h < 1 = (im,q') | M.member v im = (im,q') | otherwise = (im',q'') where ((h,v),q') = pop q im' = M.insertWith max v h im q'' = foldr (\w acc -> push w (h - digitToInt (B.index g w)) acc) q' vns vns = filter (inbound n) (sequence [north n, south n, east, west] v)