2

我必须遍历一个矩阵并说出每种类型有多少个“特征区域”。

特征区域定义为值 n 或 >n 的元素相邻的区域。

例如，给定矩阵：

0 1 2 2
0 1 1 2
0 3 0 0

有一个类型 1 的单一特征区域，它等于原始矩阵：

0 1 2 2
0 1 1 2
0 3 0 0

类型 2 有两个特征区域：

0 0 2 2    0 0 0 0
0 0 0 2    0 0 0 0
0 0 0 0    0 3 0 0

以及类型 3 的一个特征区域：

0 0 0 0 
0 0 0 0
0 3 0 0

因此，对于函数调用：

countAreas [[0,1,2,2],[0,1,1,2],[0,3,0,0]]

结果应该是

[1,2,1]

我还没有定义 countAreas，visit当我的函数没有更多可能的方块可以移动时，我被卡住了，并且没有进行正确的递归调用。我是函数式编程的新手，我仍然在摸索如何在这里实现回溯算法。看看我的代码，我能做些什么来改变它？

move_right :: (Int,Int) -> [[Int]] -> Int -> Bool
move_right (i,j) mat cond | (j + 1) < number_of_columns mat && consult (i,j+1) mat /= cond = True
               | otherwise = False

move_left :: (Int,Int) -> [[Int]] -> Int -> Bool
move_left (i,j) mat cond | (j - 1) >= 0 && consult (i,j-1) mat /= cond = True
               | otherwise = False

move_up :: (Int,Int) -> [[Int]] -> Int -> Bool
move_up (i,j) mat cond | (i - 1) >= 0 && consult (i-1,j) mat /= cond = True
               | otherwise = False

move_down :: (Int,Int) -> [[Int]] -> Int -> Bool
move_down (i,j) mat cond | (i + 1) < number_of_rows mat && consult (i+1,j) mat /= cond = True
               | otherwise = False

imp :: (Int,Int) -> Int
imp (i,j) = i


number_of_rows :: [[Int]] -> Int
number_of_rows i = length i

number_of_columns :: [[Int]] -> Int
number_of_columns (x:xs) =  length x

consult :: (Int,Int) -> [[Int]] -> Int
consult (i,j) l = (l !! i) !! j

visited :: (Int,Int) -> [(Int,Int)] -> Bool
visited x y = elem x y

add :: (Int,Int) -> [(Int,Int)] -> [(Int,Int)]
add x y = x:y

visit :: (Int,Int) -> [(Int,Int)] -> [[Int]] -> Int -> [(Int,Int)]
visit (i,j) vis mat cond | move_right (i,j) mat cond && not (visited (i,j+1) vis) = visit (i,j+1) (add (i,j+1) vis) mat cond
               | move_down (i,j) mat cond && not (visited (i+1,j) vis) = visit (i+1,j) (add (i+1,j) vis) mat cond
               | move_left (i,j) mat cond && not (visited (i,j-1) vis) = visit (i,j-1) (add (i,j-1) vis) mat cond
               | move_up (i,j) mat cond && not (visited (i-1,j) vis) = visit (i-1,j) (add (i-1,j) vis) mat cond
               | otherwise = vis
4

2 回答 2

3

在这里使用 Array 类型而不是 list-of-lists 对您有帮助吗？你还在做函数式编程，只是使用了更好的数据结构。

您可以创建一个Array (Int,Int) Int适合您的 if。看：

http://hackage.haskell.org/packages/archive/array/0.2.0.0/doc/html/Data-Array-IArray.html

import Data.Array

...获得图书馆。

于 2010-04-12T17:06:01.883 回答
1

我不认为回溯实际上是你所追求的。在我看来，您的目标是让您的visit函数建立一个访问列表，因为它从某个点找到矩阵中满足某些条件的所有连接元素。您需要考虑的是什么算法将实现这一点。不要担心用函数式或命令式编程来表达它（还）。试想一下：算法本质上是递归的吗？迭代？如果你在计算过程中停止它，你怎么知道算法接下来要做什么？你需要什么数据？

我暂时不用担心代码中的各种改进（使用Array或消除if语句等），您可以稍后再进行。您缺少的关键是可行的算法。

于 2010-04-13T01:58:58.517 回答