1

与えられた行列m、開始位置p1と終了点p2。目的は、最終的な行列に到達する方法がいくつあるかを計算することです（p2=1およびothers=0）。このため、ポジションにスキップするたびに、1つずつデクリメントします。ある位置から別の位置にスキップできるのは、水平または垂直の最大2つの位置だけです。例えば：

   m =             p1=(3,1)  p2=(2,3)
   [0 0 0]
   [1 0 4]
   [2 0 4]

あなたは位置にスキップすることができます[(3,3),(2,1)]

1つの位置からスキップすると、1つずつデクリメントして、すべてをやり直します。リストの最初の要素にスキップしましょう。このような：

    m=              
    [0 0 0]
    [1 0 4]
    [1 0 4]

これで位置(3,3)が決まり、その位置にスキップできます[(3,1),(2,3)]

そして、最終的なマトリックスまでそれを行います：

[0 0 0]
[0 0 0]
[1 0 0]

この場合、最終的な行列を取得するためのさまざまな方法の量はです20。以下の関数を作成しました。

import Data.List
type Pos = (Int,Int)
type Matrix = [[Int]]    

moviments::Pos->[Pos]
moviments (i,j)= [(i+1,j),(i+2,j),(i-1,j),(i-2,j),(i,j+1),(i,j+2),(i,j-1),(i,j-2)]

decrementsPosition:: Pos->Matrix->Matrix
decrementsPosition(1,c) (m:ms) = (decrements c m):ms
decrementsPosition(l,c) (m:ms) = m:(decrementsPosition (l-1,c) ms)

decrements:: Int->[Int]->[Int]
decrements 1 (m:ms) = (m-1):ms
decrements n (m:ms) = m:(decrements (n-1) ms)

size:: Matrix->Pos
size m = (length m,length.head $ m)

finalMatrix::Pos->Pos->Matrix
finalMatrix (m,n) p = [[if (l,c)==p then 1 else 0 | c<-[1..n]]| l<-[1..m]]

possibleMov:: Pos->Matrix->[Pos]
possibleMov p mat = checks0 ([(a,b)|a<-(dim m),b<-(dim n)]  `intersect` xs) mat
                          where xs = movements p
                               (m,n) = size mat

dim:: Int->[Int]
dim 1 = [1]
dim n = n:dim (n-1)

checks0::[Pos]->Matrix->[Pos]
checks0 [] m =[]
checks0 (p:ps) m = if ((takeValue m p) == 0) then checks0 ps m
                                               else p:checks0 ps m

takeValue:: Matrix->Pos->Int
takeValue x (i,j)= (x!!(i-1))!!(j-1)

関数の方法を作成するにはどうすればよいですか？

 ways:: Pos->Pos->Matrix->Int
4

1 に答える 1

2

可能なパスを並行して探索します。開始位置から、可能なすべての動きを行います。結果の各構成は、1 つの方法で到達できます。次に、結果の構成のそれぞれから、可能なすべての動きを行います。以前の構成のいくつかから到達できる新しい構成の数を追加します。グリッドにゼロ以外の要素が 1 つだけになるまで、この手順を繰り返します。不可能なパスを早期にカリングします。

初期構成から何通りの方法でどの構成に到達できるかを記録するには、最も簡単な方法はMap. グリッドを (ボックス化されていない) 配列として表すことにしました。

  • リストのリストよりもインデックス作成と更新の処理が簡単です
  • 使用するスペースが少なく、インデックス作成が高速です

コード：

module Ways where

import qualified Data.Map.Strict as M
import Data.Array.Unboxed
import Data.List
import Data.Maybe

type Grid = UArray (Int,Int) Int
type Position = (Int,Int)
type Configuration = (Position, Grid)
type State = M.Map Configuration Integer

buildGrid :: [[Int]] -> Grid
buildGrid xss
    | null xss || maxcol == 0   = error "Cannot create empty grid"
    | otherwise = listArray ((1,1),(rows,maxcol)) $ pad cols xss
      where
        rows = length xss
        cols = map length xss
        maxcol = maximum cols
        pad (c:cs) (r:rs) = r ++ replicate (maxcol - c) 0 ++ pad cs rs
        pad _ _ = []

targets :: Position -> [Position]
targets (i,j) = [(i+d,j) | d <- [-2 .. 2], d /= 0] ++ [(i,j+d) | d <- [-2 .. 2], d /= 0]

moves :: Configuration -> [Configuration]
moves (p,g) = [(p', g') | p' <- targets p
                        , inRange (bounds g) p'
                        , g!p' > 0, let g' = g // [(p, g!p-1)]]

moveCount :: (Configuration, Integer) -> [(Configuration, Integer)]
moveCount (c,k) = [(c',k) | c' <- moves c]

step :: (Grid -> Bool) -> State -> State
step okay mp = foldl' ins M.empty . filter (okay . snd . fst) $ M.assocs mp >>= moveCount
  where
    ins m (c,k) = M.insertWith (+) c k m

iter :: Int -> (a -> a) -> a -> a
iter 0 _ x = x
iter k f x = let y = f x in y `seq` iter (k-1) f y

ways :: Position -> Position -> [[Int]] -> Integer
ways start end grid
    | any (< 0) (concat grid)   = 0
    | invalid   = 0
    | otherwise = fromMaybe 0 $ M.lookup target finish
      where
        ini = buildGrid grid
        bds = bounds ini
        target = (end, array bds [(p, if p == end then 1 else 0) | p <- range bds])
        invalid = not (inRange bds start && inRange bds end && ini!start > 0 && ini!end > 0)
        okay g = g!end > 0
        rounds = sum (concat grid) - 1
        finish = iter rounds (step okay) (M.singleton (start,ini) 1)
于 2012-10-14T01:01:27.120 に答える