Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import qualified Data.Matrix as Matrix
- import qualified Data.Vector as Vector
- import Data.Typeable
- import Debug.Trace
- import qualified Data.Maybe as Maybe
- import qualified Control.Monad as Monad
- -- inp = Matrix.fromLists [[0, 5, 8, 10, 0, 0, 3, 6],
- -- [5, 0, 2, 0, 0, 0, 0, 1],
- -- [8, 2, 0, 4, 5, 6, 0, 7],
- -- [10, 0, 4, 0, 12, 9, 7, 0],
- -- [0, 0, 5, 12, 0, 9, 0, 12],
- -- [0, 0, 6, 9, 9, 0, 8, 0],
- -- [3, 0, 0, 7, 0, 8, 0, 2],
- -- [6, 1, 7, 0, 12, 0, 2, 0]]
- consoleInput = do
- input <- getLine
- inputs <- Monad.replicateM (read input :: Int) getLine
- map (\(str) -> read str ::[Int]) inputs
- matrixShift :: Matrix.Matrix Int -> Matrix.Matrix (Maybe Int)
- matrixShift mat =
- Matrix.matrix
- (Matrix.nrows mat)
- (Matrix.ncols mat)
- (\(i,j) ->
- let elem = Matrix.getElem i j mat
- in
- if elem == 0 then
- Nothing
- else
- Just elem
- )
- -- matrRead :: [[ Int ]]
- -- matrRead = read
- main = do
- let inp = Matrix.fromLists consoleInput
- print inp
- print $ solve (matrixShift inp)
- folding :: Maybe([Int], Int) -> Maybe([Int], Int) -> Maybe([Int], Int)
- folding (Just sum) (Just curr) =
- if snd(sum) < snd(curr) then
- Just sum
- else
- Just curr
- folding Nothing (Just curr) =
- Just curr
- folding Nothing Nothing =
- Nothing
- folding (Just sum) Nothing =
- Just sum
- enumerate :: [Maybe Int] -> [(Int, Maybe Int)]
- enumerate row =
- map (\(x, y) -> ((fromInteger x), y)) (zip [1..] row)
- solve_step :: Matrix.Matrix(Maybe Int) -> [Int] -> Int -> Int -> Maybe ([Int], Int)
- solve_step matr way n curr =
- if (length way) == (Matrix.ncols matr) then
- -- trace ("way: " ++ show way ++ "cur: " ++ show curr) $
- Just (way, curr)
- else
- foldl
- folding
- Nothing
- (
- map
- (\ (ind, val) ->
- solve_step
- matr
- (way ++ [ind])
- ind
- (curr + val)
- )
- (
- map
- (\ (ind , Just val) ->
- (ind, val)
- )
- (
- filter
- (\
- (ind, val) ->
- if (length way) == ((Matrix.nrows matr) - 1) then
- (ind == 1) && (Maybe.isJust val)
- else
- (not $ elem ind way) && (not $ ind == 1) && (Maybe.isJust val)
- )
- (enumerate row)
- )
- )
- )
- where row = Vector.toList (Matrix.getRow n matr)
- solve matr = solve_step matr [] 1 0
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement