0

可能重复：
Haskell - 操作列表

给定一个矩阵m，一个起点p1和一个终点p2。目标是计算有多少种方法可以到达最终矩阵（p2=1 和其他=0）。为此，每次您跳到某个位置时，您都会减一。您最多只能从一个位置跳到另一个位置，水平或垂直两个位置。例如：

   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解决的功能？

4

1 回答 1

0

在我认识到正在玩的游戏是多个令牌弹珠之后，我知道计算从开始到结束的路径数是通过扩展游戏树来完成的，如果找到的棋盘是结束棋盘，那么将其计为其他路径明智的不要。

因此，我随后看到您的功能仅在第一个可能的移动s中以一种方式扩展棋盘，而不是在所有可能的移动中。正确的版本将测试棋盘是否处于最终状态并返回 1，否则将所有可能的移动的循环结果相加，如果该移动无效，则为计数或 0。

于 2012-10-16T03:18:17.490 回答