algorithm - 使用 haskell 打印所有可能的路径

Question

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

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

 +---+
 | > |  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"

Answer 1

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

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

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

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