fork(1) download
copy 
  1.  
  2. -- 反向路径，由(x,y)点反推回(0,0)坐标点, x y 参数为最大坐标点
  3. rpaths_point x y 
  4.     | x < 0 || y < 0   = [[]]
  5.     | x == 0 && y == 0 = [[(0,0)]]
  6.     | x > 0  && y == 0 = map ((x, y):)  (rpaths_point (x-1) y)
  7.     | x == 0 && y > 0  = map ((x, y):)  (rpaths_point x (y-1))
  8.     | otherwise  = map ((x,y):) (rpaths_point (x-1) y ++ rpaths_point x (y-1))
  9.  
  10.  
  11. -- 正向路径 rows cols 为矩阵长度
  12. paths rows cols = map reverse $ rpaths_point (rows-1) (cols-1)
  13.  
  14. -- 求最大值
  15. max_path_sum mat = maximum $ map (\r -> sum $ map (\p -> matrix !! fst p !! snd p) r) walks
  16.     where 
  17.         walks = paths (length mat) $ length $ head mat
  18.  
  19. matrix = [[0, 0, 8, 0, 0], [0, 0, 0, 9, 0], [0, 7, 0, 0, 0], [0, 0, 6, 0, 0]]
  20.  
  21. main = do
  22.         -- 4x5矩阵所有可能路径
  23.         print $ paths (length matrix) $ length $ head matrix
  24.         -- 矩阵路径之和最大值
  25.         putStrLn $ "max sum of " ++ (show matrix) ++ " = " ++ show (max_path_sum matrix)
  26.  
Success #stdin #stdout 0s 4704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[[(0,0),(0,1),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4)],[(0,0),(0,1),(0,2),(0,3),(1,3),(1,4),(2,4),(3,4)],[(0,0),(0,1),(0,2),(1,2),(1,3),(1,4),(2,4),(3,4)],[(0,0),(0,1),(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)],[(0,0),(1,0),(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)],[(0,0),(0,1),(0,2),(0,3),(1,3),(2,3),(2,4),(3,4)],[(0,0),(0,1),(0,2),(1,2),(1,3),(2,3),(2,4),(3,4)],[(0,0),(0,1),(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)],[(0,0),(1,0),(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)],[(0,0),(0,1),(0,2),(1,2),(2,2),(2,3),(2,4),(3,4)],[(0,0),(0,1),(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)],[(0,0),(1,0),(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)],[(0,0),(0,1),(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)],[(0,0),(1,0),(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)],[(0,0),(1,0),(2,0),(2,1),(2,2),(2,3),(2,4),(3,4)],[(0,0),(0,1),(0,2),(0,3),(1,3),(2,3),(3,3),(3,4)],[(0,0),(0,1),(0,2),(1,2),(1,3),(2,3),(3,3),(3,4)],[(0,0),(0,1),(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)],[(0,0),(1,0),(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)],[(0,0),(0,1),(0,2),(1,2),(2,2),(2,3),(3,3),(3,4)],[(0,0),(0,1),(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)],[(0,0),(1,0),(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)],[(0,0),(0,1),(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)],[(0,0),(1,0),(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)],[(0,0),(1,0),(2,0),(2,1),(2,2),(2,3),(3,3),(3,4)],[(0,0),(0,1),(0,2),(1,2),(2,2),(3,2),(3,3),(3,4)],[(0,0),(0,1),(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)],[(0,0),(1,0),(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)],[(0,0),(0,1),(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)],[(0,0),(1,0),(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)],[(0,0),(1,0),(2,0),(2,1),(2,2),(3,2),(3,3),(3,4)],[(0,0),(0,1),(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)],[(0,0),(1,0),(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)],[(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(3,3),(3,4)],[(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(3,3),(3,4)]]
max sum of [[0,0,8,0,0],[0,0,0,9,0],[0,7,0,0,0],[0,0,6,0,0]] = 17
https://ideone.com/Ny0GKc
language:
Haskell (ghc 8.4.4)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!