回溯到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語句等），您可以稍後獲取它們。你缺少的關鍵是一個可行的算法。