route.hs

import Control.Applicative

goodRoute :: (Real a) => [[a]] -> [a]
goodRoute = n . goodRoute_
    where
        goodRoute_ :: (Real a) => [[a]] -> Maybe [a]
        goodRoute_ ([]:_) = Nothing
        goodRoute_ [] = Nothing
        goodRoute_ ((x:[]):[]) = Just (x:[])
        goodRoute_ matrix =
            (:) <$> (Just $ (head . head) matrix)
                <*> betterRoute ((goodRoute_ . dropRow) matrix) ((goodRoute_ . dropCol) matrix)

        betterRoute :: (Real a) => Maybe [a] -> Maybe [a] -> Maybe [a]
        betterRoute Nothing b@(Just routeB) = b
        betterRoute a@(Just routeA) Nothing = a
        betterRoute a@(Just routeA) b@(Just routeB)
            | sum routeA > sum routeB = a
            | otherwise = b

        dropRow m = tail m
        dropCol m = map tail m

        n Nothing = []
        n (Just a) = a

main = do
    let matrix = 
            [
                [8,1,4,5,5],
                [3,5,2,7,8],
                [2,4,3,2,3],
                [4,6,7,7,1],
                [9,9,1,9,3]
            ]
    mapM putStrLn $ map show $ goodRoute matrix

課題

初めて質問させていただきます。 
どうぞよろしくお願いします。 
 
下記のように1から9までの数字が、ランダムにA1から並んでいます。 
 
     Ａ Ｂ Ｃ Ｄ Ｅ・・・・・・・・・・ 
1} 8 1 4 5 5 ・・・・・・・・・・ 
2} 3 5 2 7 8 ・・・・・・・・・・ 
3} 2 4 3 2 3 ・・・・・・・・・・ 
4} 4 6 7 7 1 ・・・・・・・・・・ 
5} 9 9 1 9 3 ・・・・・・・・・・ 
・ 
・ 
与えられた範囲の一番左上のセルからスタートし、一番右下のセルまで一つずつセル移動していく。 
セルの移動は右または下にしか移動できない。 
 
この時、経路内のセルの数値の合計が最大となる経路を求めセルを着色し最大値を示せ。 
・ 
課題 1) 
 A1:E5 (5行x5列)の範囲を考える。 
 70の経路が考えられるが、全ての経路を求め合計値を計算し最大値及び経路を求める。 
 これを For～Next文を用いてプログラミングせよ。 
 
課題 2) 
 A1:J10 (10行x10列)の範囲を考える。 
 48,620の経路が考えられるが、同様に最大値及びその経路を求める。 
 ただし課題1を参考にして再帰処理を用いてプログラミングせよ。 
 
課題 3) 
 A1:T20 (20行x20列)の範囲を考える。 
 経路数は350億を超える。 
 課題2のプログラムを改良し、妥当な時間で処理が完了するプログラムを作れ。 
 
以上が課題ですが、経路をどう網羅的にはじき出すのか、色々考えてはみたのですがうまい方法が見つからず、とっかかりが掴めません。 
 
何かヒントを頂けるとありがたいです。