可能重複的名單:
Haskell - Manipulating lists操縱名單
給定矩陣m
,起始位置p1
和最後一點p2
。 目標是計算有多少種方法可以達到最終矩陣(p2 = 1,其他= 0)。爲此,每次跳到某個位置時,都會減1。 您最多隻能在兩個位置(水平或垂直)從一個位置跳到另一個位置。例如:
m = p1=(3,1) p2=(2,3)
[0 0 0]
[1 0 4]
[2 0 4]
可以跳到位置[(3,3),(2,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]]
s::Pos->Pos->Matrix->Int
s (i,j) fim mat = if (mat == (matrizFinal (tamanho mat) fim)) then 1
else if (possiveisMov (i,j) mat)/= [] then s (head(possiveisMov (i,j) mat)) fim (decrementaPosicao (i,j) mat)
else 0
matrizFinal:: Pos->Pos->Matrix
matrizFinal (m,n) p = [[if (y,x)==p then 1 else 0 | x<-[1..n]]| y<-[1..m]]
movimentos::Pos->[Pos]
movimentos (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)]
decrementaPosicao:: Pos->Matrix->Matrix
decrementaPosicao (1,c) (m:ms) = (decrementa c m):ms
decrementaPosicao (l,c) (m:ms) = m:(decrementaPosicao (l-1,c) ms)
decrementa:: Int->[Int]->[Int]
decrementa 1 (m:ms) = (m-1):ms
decrementa n (m:ms) = m:(decrementa (n-1) ms)
tamanho:: Matrix->Pos
tamanho m = (length m,length.head $ m)
possiveisMov:: Pos->Matrix->[Pos]
possiveisMov p mat = verifica0 ([(a,b)|a<-(dim m),b<-(dim n)] `intersect` xs) mat
where xs = movimentos p
(m,n) = tamanho mat
dim:: Int->[Int]
dim 1 = [1]
dim n = n:dim (n-1)
verifica0::[Pos]->Matrix->[Pos]
verifica0 [] m =[]
verifica0 (p:ps) m = if ((pegaAltura m p) == 0) then verifica0 ps m
else p:verifica0 ps m
pegaAltura:: Matrix->Pos->Int
pegaAltura x (i,j)= (x!!(i-1))!!(j-1)
有誰知道爲什麼功能s
不指望有許多辦法來解決這個問題呢?我該如何解決這個問題,或者更好的方法來解決這個功能s
?