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 には 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 の 1 つの特徴的な領域:

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 (Int,Int) Intあなたはそれがあなたのために働く場合を作成することができます。見る：

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 に答える