1

左、右、上方向にのみ移動することで得られる、与えられたマトリックス内のすべての可能なパスを描画するプログラムを作成する必要があります。同じ場所を2回以上横断しないでください。また、特定のパスでは、すべての可能な方向にモーションを使用する場合と使用しない場合があることに注意してください。

パスは、マトリックスの左下隅から始まり、右上隅に到達します。次の記号は、現在の位置でのモーションの方向を示すために使用されます。

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

シンボル*は、パスの終わりを示すために最終的な場所で使用されます。

例:

5x8マトリックスの場合、左、右、上方向を使用して、2つの異なるパスを以下に示します。

パス1:

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

パス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 のセルが 1 つだけ含まれます。各 UP セルが選択されると、LEFT と RIGHT と EMPTY のセルを決定できると主張します。一番上以外の各行のすべての可能なセルは、すべての組み合わせで UP になる可能性があると主張します。

したがって、各パスは、UP セルを決定する範囲 (1..列) 内の (rows-1) 長さの数値リストに同形です。したがって、許可されるパスの数は column^(rows-1) であり、この形式で可能なパスを列挙するのは簡単です。

次に、この形式を ASCII アートに変換するプリンターを作成できます。スキルレベルによっては、これは面倒かもしれません。

于 2012-12-14T12:24:01.087 に答える
1

宿題のように見えるので、十分なヒントを与えようとします

  • 最初に、セルから目標までのパスの数を埋めてみてください。

そう

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

ここで注意すべきことは、最上位レベルのセルから へのパスが常に 1 つあるということ*です。

  • 同じ行のセルからの可能なパスの数は同じになります。ダウン アクションがないため、すべてのパスが最終的に上に移動する必要があるため、これを実現できます。そのため、現在の行の上のセルは現在の行の任意のセルに到達できます。

  • 現在のセルからのすべての可能なパスは、左、右、および上のセルからの可能なパスと関係があることがわかります。しかし、私たちが知っているように、行内の 1 つのセルのみからすべての可能なパスを見つけることができ、残りのセルの可能なパスは、同じ行のいくつかの動きの後にそのセルからの可能なパスの接尾辞が続きます。

たぶん私はあなたに例を挙げます

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

最初の行のセルからすべての可能なパスを知っています。2行目でも同じものを見つける必要があります。したがって、適切な戦略は、最も右側のセルに対してそれを行うことです

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

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

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

同じ行の残りのセルについてこれを見つけることは、前に述べたように、これらを使用して簡単です。

最後に、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)
  • 有効なパスは、徹底的に検索できる this の順列のプレフィックスになります。permutationsfromを使用しData.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し、印刷可能な文字に es することができます...それをいじってみると、いくつかのアイデアが得られるかもしれません。GridStatus

于 2012-12-14T05:39:28.237 に答える