解题思路

1. 使用了 map 记录走过的点, 请问大佬们一般咋做，有没有更好的方式
2. dp 递推方式为依次组合每个点的 state monad, 请问大佬们一般咋做，有没有更好的方式

代码如下

module Main where

import Control.Monad.State (MonadState (get, put), State)
import Control.Monad.State.Lazy (runState)
import Data.List (foldl1')
import qualified Data.Map as M
import Data.Maybe (fromMaybe)

main :: IO ()
main = do
  [bx, by, horsex, horsey] <- fmap read . words <$> getContents
  let horses = calculateHorsePositions (horsex, horsey)
      dpState = memoizedDp horses <$> [(x, y) | x <- [0 .. bx], y <- [0 .. by], not $ (x, y) `elem` [(0, 0), (0, 1), (1, 0)]]
      ans = foldl1' (>>) dpState
  putStrLn . show . fst $ runState ans (M.fromList [((0, 1), if (0, 1) `elem` horses then 0 else 1), ((1, 0), if (1, 0) `elem` horses then 0 else 1)])

type Position = (Int, Int)

calculateHorsePositions :: Position -> [Position]
calculateHorsePositions (x, y) =
  filter (\(x', y') -> x' >= 0 && y' >= 0) . ((x, y) :) $
    [((af x an), (sf y sn)) | let f = [(+), (-)], af <- f, sf <- f, let n = [1, 2], an <- n, sn <- n, an /= sn]

type Cache = M.Map Position Integer

type HorsePosition = [Position]

memoizedDp :: HorsePosition -> Position -> State Cache Integer
memoizedDp horses p@(x, y) = do
  cache <- get
  let merge =
        if p `elem` horses
          then 0
          else
            getPre (x - 1, y) cache + getPre (x, y - 1) cache
  put $ M.insert p merge cache
  return merge
  where
    getPre pp pCache = fromMaybe 0 (M.lookup pp pCache)