回溯到haskell

Question

我必须遍历一个矩阵，并说出它有多少个“特征区域”。

特征区域被定义为值为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 

Answer 1

它会帮助你在这里使用数组类型，而不是列表清单？你还在做功能性编程，只是使用更好的数据结构。

如果这对您有用，您可以创建一个Array (Int,Int) Int。请参阅：

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

import Data.Array 

...获得库。

Answer 2

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

我不担心现在的代码中的各种改进（使用Array或删除if语句等），您可以稍后获取它们。你缺少的关键是一个可行的算法。