解题思路用了 dfs 参考的 题解 P1004 【方格取数】 - 洛谷专栏

• 一开始也想写 dp 来, 但是不知道如何使用 haskell 实现这复杂的 dp, 请问大佬们是如何做的
• 写 dfs 时, 经常搞反方向...这次代码写的就很奇怪, 写成了从 (n,n) 走到 (0,0), 调试的时候属实折磨到吐血
• 还有一些疑问，如果有多个状态需要修改和记录，一般怎么做？现在我的想法是追加到一个(,,,)里，请问这是标准做法吗？

衷心感谢每一位愿意花费宝贵时间阅读此文并提出宝贵建议的大佬们。

dfs 实现代码如下

module Main where

import Control.Monad.Reader (MonadReader (ask), ReaderT (runReaderT))
import Control.Monad.State (MonadState (get), State, evalState, modify)
import qualified Data.Map as M
import Data.Maybe (fromMaybe)

main :: IO ()
main = do
  n <- read <$> getLine :: IO Int
  weightedPoints <- getAllWeightedPoint
  putStrLn . show
    . flip evalState mempty
    . flip runReaderT (weightedPoints, (n, n))
    $ (dfs (1, 0) (1, 0))

type Point = (Int, Int)

type WeightedPoints = M.Map Point Int {- Weight -}

getAllWeightedPoint :: IO WeightedPoints
getAllWeightedPoint =
  M.fromList <$> getAllLines
  where
    getAllLines = do
      point@[x, y, weight] <- fmap read . words <$> getLine :: IO [Int]
      if point /= [0, 0, 0]
        then (((x, y), weight) :) <$> getAllLines
        else return []

type Cache = M.Map (Point, Point) Int

dfs :: Point -> Point -> (ReaderT (WeightedPoints, Point) (State Cache) Int)
dfs pfst@(xfst, yfst) psnd@(xsnd, ysnd) = do
  cache <- get
  (weightedPoints, targetPoint) <- ask
  case M.lookup (pfst, psnd) cache of
    Just v -> return v
    Nothing -> do
      dd <- nextStep (xfst + 1, yfst) (xsnd + 1, ysnd)
      dr <- nextStep (xfst + 1, yfst) (xsnd, ysnd + 1)
      rd <- nextStep (xfst, yfst + 1) (xsnd + 1, ysnd)
      rr <- nextStep (xfst, yfst + 1) (xsnd, ysnd + 1)
      let max' = maximum [dd, dr, rd, rr]
      modify $ M.insert (pfst, psnd) max'
      return max'
      where
        nextStep pnfst pnsnd =
          if isPointInBounds pnfst targetPoint && isPointInBounds pnsnd targetPoint
            then (addWeight pnfst) . (if (pnfst /= pnsnd) then (addWeight pnsnd) else id) <$> dfs pnfst pnsnd
            else return $ 0
        addWeight p = (+) . fromMaybe 0 $ M.lookup p weightedPoints

isPointInBounds :: Point -> Point -> Bool
isPointInBounds (x, y) (bx, by) = x > 0 && x <= bx && y > 0 && y <= by