1

我需要编写一个程序来绘制给定矩阵中的所有可能路径，这些路径可以通过仅向左、向右和向上移动来获得。一个人不应多次穿越同一地点。另请注意，在特定路径上，我们可能会或可能不会在所有可能的方向上使用运动。

路径将从矩阵的左下角开始，并到达右上角。以下符号用于表示当前位置的运动方向：

 +---+
 | > |  right
 +---+
 +---+
 | ^ |  up
 +---+
 +---+
 | < |  left
 +---+

该符号*用于最终位置以指示路径的结束。

例子：

对于 5x8 矩阵，使用左、右和上方向，下面显示了 2 条不同的路径。

路径一：

 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   | * |
 +---+---+---+---+---+---+---+---+
 |   |   | > | > | > | > | > | ^ |
 +---+---+---+---+---+---+---+---+
 |   |   | ^ | < | < |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   | > | > | > | ^ |   |   |   |
 +---+---+---+---+---+---+---+---+
 | > | ^ |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+

路径 2

 +---+---+---+---+---+---+---+---+
 |   |   |   | > | > | > | > | * |
 +---+---+---+---+---+---+---+---+
 |   |   |   | ^ | < | < |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   | ^ |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   | > | > | > | ^ |   |   |
 +---+---+---+---+---+---+---+---+
 | > | > | ^ |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+

谁能帮我这个？

我尝试使用列表来解决。我很快意识到我正在制造一场灾难。这是我尝试过的代码。

 solution x y = travel (1,1) (x,y) 
 travelRight (x,y) = zip [1..x] [1,1..] ++ [(x,y)] 
 travelUp (x,y) = zip [1,1..] [1..y] ++ [(x,y)]
 minPaths = [[(1,1),(2,1),(2,2)],[(1,1),(1,2),(2,2)]]

 travel startpos (x,y) = rt (x,y) ++ up (x,y)

 rt (x,y) | odd y = map (++[(x,y)]) (furtherRight (3,2) (x,2) minPaths)
          | otherwise = furtherRight (3,2) (x,2) minPaths
 up (x,y) | odd x = map (++[(x,y)]) (furtherUp (2,3) (2,y) minPaths)
          | otherwise = furtherUp (2,3) (2,y) minPaths

 furtherRight currpos endpos paths | currpos == endpos = (travelRight currpos) : map (++[currpos]) paths
                                   | otherwise = furtherRight (nextRight currpos) endpos ((travelRight currpos) : (map (++[currpos]) paths))
 nextRight (x,y) = (x+1,y)

 furtherUp currpos endpos paths | currpos == endpos = (travelUp currpos) : map (++[currpos]) paths
                                | otherwise = furtherUp (nextUp currpos) endpos ((travelUp currpos) : (map(++[currpos]) paths))
 nextUp (x,y) = (x,y+1)

 identify lst = map (map iden) lst
 iden (x,y) = (x,y,1)


 arrows lst = map mydir lst
 mydir (ele:[]) = "*"
 mydir ((x1,y1):(x2,y2):lst) | x1==x2 = '>' : mydir ((x2,y2):lst)
                             | otherwise = '^' : mydir ((x2,y2):lst)

 surroundBox lst = map (map createBox) lst
 bar = "+    -+"
 mid x = "| "++ [x] ++" |"
 createBox chr = bar ++ "\n" ++ mid chr ++ "\n" ++ bar ++ "\n"
4

3 回答 3

3

这个 ASCII 网格比启发性更令人困惑。让我描述一种更好的方式来表示每条可能的路径。

每个非顶行将恰好有一个带有 UP 的单元格。我声称一旦选择了每个 UP 单元格，就可以确定 LEFT、RIGHT 和 EMPTY 单元格。我声称每个非顶行中的所有可能的单元格都可以在所有组合中为 UP。

因此，每条路径都与确定 UP 单元格的范围（1..columns）中的（行-1）长度的数字列表同构。因此，允许路径的数量是 columns^(rows-1) 并且以这种格式枚举可能的路径应该很容易。

然后您可以制作一台将这种格式转换为 ASCII 艺术的打印机。这可能很烦人，具体取决于技能水平。

于 2012-12-14T12:24:01.087 回答
1

看起来像一个家庭作业，所以我会尽量给出足够的提示

  • 尝试首先填充从单元格到目标的路径数。

所以

 +---+---+---+---+---+---+---+---+
 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | * |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+

这里要注意的是，从顶层的单元格到*.

  • 同一行中单元格的可能路径数将相同。您可以意识到这一点，因为所有路径最终都必须向上移动，因为没有向下操作，因此在任何路径中，当前行中的任何单元格都可以到达当前行上方的单元格。

  • 您可以感觉到当前单元格的所有可能路径与左、右和上方单元格的可能路径有关系。但正如我们所知，我们可以从一行中的一个单元格中找到所有可能的路径，其余单元格的可能路径将是同一行中的一些移动，然后是来自该单元格的可能路径的后缀。

也许我会给你一个例子

 +---+---+---+
 | 1 | 1 | * | 
 +---+---+---+
 |   |   |   |  
 +---+---+---+
 |   |   |   |   
 +---+---+---+

您知道来自第一行单元格的所有可能路径。您需要在第二行中找到相同的内容。所以一个好的策略是为最正确的细胞做这件事

 +---+---+---+
 | > | > | * | 
 +---+---+---+
 | ^ | < | < |  
 +---+---+---+
 |   |   |   |   
 +---+---+---+

 +---+---+---+
 |   | > | * | 
 +---+---+---+
 |   | ^ | < |  
 +---+---+---+
 |   |   |   |   
 +---+---+---+

 +---+---+---+
 |   |   | * | 
 +---+---+---+
 |   |   | ^ |  
 +---+---+---+
 |   |   |   |   
 +---+---+---+

现在，正如我之前所说，使用这些为同一行中的其余单元格找到这个是微不足道的。

最后，如果您有m X n矩阵，则从左下角到右上角的路径数将为n^(m-1).

另一种方式

这种方式不是很理想，但很容易实现。考虑m X n网格

  • 找到最长的路径。您不需要确切的路径，只需要<, >, ^. m您可以根据和找到直接公式n。

喜欢

 ^ = m - 1
 < = (n-1) * floor((m-1)/2) 
 > = (n-1) * (floor((m-1)/2) + 1)
  • 任何有效路径都将是其排列的前缀，您可以对其进行详尽搜索。使用permutationsfromData.List获取所有可能的排列。然后制作一个给定路径的函数，从中剥离有效路径。将其映射到排列列表并删除重复项。需要注意的是路径将是您从排列中获得的前缀，因此同一路径可以有多个排列。
于 2012-12-14T05:08:30.103 回答
0

您可以创建该矩阵并定义“字段”吗？即使你不能（给出了一个特定的矩阵），你也可以将一个[(Int, Int)]矩阵（这对于这种任务听起来很合理）映射到你自己的表示中。

由于您没有指定您的技能水平，我希望您不介意我建议您首先尝试创建某种网格以便进行一些工作：

data Status = Free | Left | Right | Up
    deriving (Read, Show, Eq)
type Position = (Int, Int)
type Field = (Position, Status)
type Grid = [Field]

grid :: Grid
grid = [((x, y), stat) | x <- [1..10], y <- [1..10], let stat = Free]

当然，还有其他方法可以实现这一点。之后你可以定义一些动作，映射Position到Grid索引和Statuses 到可打印的字符......试着摆弄它，你可能会得到一些想法。

于 2012-12-14T05:39:28.237 回答