Bibi the Smart Frog is playing a jumping game on an m x n rectangular board. There is a number written in each cell of the board (Bibi can read these numbers since he is very smart!) Bibi starts the game by picking any cell on the board and stays there. At each step, Bibi will jump to another cell. He can either: Jump to the right to a cell in t…

gistfile1.hs

import Data.Array
import Data.List
 
data Direction = DRight | DDown
 
isValid (a, b) board = a >= 0 && a <= m && b >= 0 && b <= n where
  (_, (m, n)) = bounds board
 
canMove board (a, b) (DRight, step) = isValid (a, b + step) board &&
  board ! (a, b + step) >= board ! (a, b)
canMove board (a, b) (DDown, step) = isValid (a + step, b) board &&
  board ! (a + step, b) <= board ! (a, b)
 
offsetIndex (x, y) (DRight, step) = (x, y + step)
offsetIndex (x, y) (DDown, step)  = (x + step, y)
 
maxPathLengthAt board currLength index = 
  if null possibleMoves then currLength else maximum . map moveForward $ possibleMoves where
  possibleMoves = map (offsetIndex index) . filter (canMove board index) $ possibleDirections
  moveForward next = maxPathLengthAt board (currLength + 1) next
  possibleDirections = map (\step -> (DDown, step)) [1..(m - x)] ++ 
                       map (\step -> (DRight, step)) [1..(n - y)]
  (x, y) = index
  (_, (m, n)) = bounds board
 
maxPathLength board = maximum . map (maxPathLengthAt board 1) $ indices where
  indices = [(i, j) | i <- [0 .. m], j <- [0 .. n]]
  (_, (m, n)) = bounds board
 
main = do
  testsStr <- getLine
  let tests = read testsStr
  boards <- sequence $ map (const readBoard) [1..tests]
  let maxPaths = map maxPathLength boards
  sequence $ map (putStrLn . show) maxPaths
 
readBoard :: IO (Array (Integer, Integer) Integer)
readBoard = do
  size <- getLine
  let m:n:_ = map read $ words size
  rowsStr <- sequence $ map (const getLine) [1..m]
  let numList = concat $ map (map read) $ map words rowsStr
  return $ listArray ((0, 0), (m - 1, n - 1)) numList

{-
Sample run: http://ideone.com/5hxu0V
Example

Input:
  2

  2 3
  2 1 1
  2 1 1

  4 4
  6 2 5 2
  4 5 3 8
  9 7 8 9
  9 9 9 5

Output:
  3
  5
-}