import Data.Tuple import Data.List import Data.Bits import Data.Maybe import Control.Exception import qualified Data.HashMap.Strict as Map main = interact $ unlines . sol . allInt . lines data Move = UL | UR | R | LR | LL | L | Nil deriving (Eq, Read, Show) type Point = (Int, Int) type Cboard = Map.HashMap Point Move (.+) (x,y) (u,v) = (x+u, y+v) (.-) (x,y) (u,v) = (x-u, y-v) moves = [((-2,-1),UL),((-2,1),UR),((0,2),R), ((2,1),LR),((2,-1),LL),((0,-2),L)] :: [(Point, Move)] sol [[n],[sx,sy,fx,fy]] = let res = bfs n (fx,fy) [(sx,sy)] [] $ Map.fromList [((sx,sy), Nil)] in case res of Nothing -> [ "Impossible" ] Just xs -> [ show $ length xs, unwords $ map show xs ] check n (x,y) = 0<=x && 0<=y && x Point -> [Point] -> [Point] -> Cboard -> Maybe [Move] bfs _ _ [] [] board = Nothing bfs n fp [] qs board = bfs n fp (reverse qs) [] board bfs n fp (p:ps) qs board | p == fp = Just $ reverse $ genPath p board | otherwise = bfs n fp ps qs' board' where next = filter (\(p',_) -> check n p' && (not $ Map.member p' board)) $ map (\(p',m) -> (p'.+p,m)) moves board' = foldl (\b (p,m)->Map.insert p m b) board next qs' = (reverse $ map fst next) ++ qs genPath p board = case Map.lookup p board of Just Nil -> [] Just m -> m : genPath (p .- (fromJust $lookup m $map swap moves)) board -------------------------------------------------------------------------------- groupOn :: Int -> [a] -> [[a]] groupOn _ [] = [] groupOn n xs = let (sts, nds) = splitAt n xs in sts : groupOn n nds fromBool :: Num a => Bool -> a fromBool b = if b then 1 else 0 allInt :: [String] -> [[Int]] allInt = map ((map read) . words) swrt :: Ord a => (a, a) -> (a, a) swrt (a, b) | compare b a == LT = (b, a) | otherwise = (a, b) toSingle :: a -> [a] toSingle x = [x] --------------------------------------------------------------------------------