1

0 と 1 を含む nxn 正方行列が与えられます。0 はブロックされたセルを意味し、1 はロボットが歩けるオープン セルを意味します。ロボットが最初に (0,0) にある場合、(n-1,n-1) に到達する方法はいくつありますか。
ロボットは上下左右に移動できます。パスは別個である必要があります。ループがある場合と同様に、パスを無限ではなく 1 として計算できます。たとえば、7x7 マトリックスの答えです。

1 1 0 1 1 0 1
0 1 0 0 1 1 1
1 1 1 0 1 0
0 1 0 1 1 1
0 1 0 0 1 0 1
0 1 1 1 0 1
0 0 0 0 1 1 1

は4

4つのパス は 次 の
とおり です
。0 _ _ _ _ 0 1 1 0 1 0 _ 0 1 1 1 1 _ 1 0 1 0 0 _ 0 1 _ _ 0 _ 0 0 _ 0 0 _ _ _ 0 _ 0 0 0 0 1 1 _ _ 0 1 1 0 1 0 _ 0 1 1 1 1 _ _ 0 1 0 0 1 0 _ _ 1 1 0 1 0 0 _ 0 1 0 1 1 1 _ 0 1 0 0 0 0 _ _ _ _ 0 1 1 0 1 0 _ 0 0 1 1 1 1 _ _ 0 1 0 0 1 0 _ _ _ 0 1 0 0 1 0 _ 0 1 1 1 0 _ 0 0 0 0 1 1 _






























ロボットが右と下にのみ移動できる場合に dp を使用して問題を解決しました。同じだけのアルゴリズムで私を助けてください。これをグラフに変換して、何らかのアルゴリズムを適用する必要がありますか。

4

1 に答える 1

3

たどったパスのメモリを使用してDFSを実行する必要があると思います。擬似コードでは、次のようになります。

DFS(matrix, path):
   /* End conditions */
   If path.last is [n-1, n-1]
      print path /* Hooray! Found a path! */
   If path.last has already been visited in path
      Discard solution
   If path.last is out of bounds (coordinates < 0 or > n-1)
      Discard solution
   If matrix[path.last] value is 0
      Discard solution

   /* We're in the middle of a path: continue exploring */
   For direction in [1, 0], [0, 1], [-1, 0], [0, -1]
      Add [path.last + direction] to path // Move north, south, east, west
      DFS(matrix, path)
      Remove last element from path

/* Call the algorithm */
DFS(matrix, [1, 1])

このアルゴリズムでは、マトリックスとパスへの参照を渡すことができます。これにより、一定のメモリ アルゴリズムが得られます ( patharound のインスタンスは 1 つしかありません)。時間の複雑さに関しては、これは可能なパスの数に対して線形になり(却下されたものも含め、可能なパスを 1 回ずつ探索するため)、その長さに対しては 2次になります (ポイントごとに、それが既に存在するかどうかをテストするため)。線形検索によるパス)。パスの数は で指数関数的になる可能性が nあり、パスの長さは最悪の場合、 になることに注意してくださいn^2。非常に遅いブルート フォース アルゴリズム。

このアルゴリズムの最悪のケースは、指数関数的な複雑さを持つものだけで満たされた行列です。

最良のケースは、 と の間[1, 1]に可能なパスが 1 つしかない行列[n-1, n-1]です。その場合、パスの長さに複雑さがあり、 と の間になる可能性がO(n)ありO(n^2)ます。

于 2012-10-24T20:57:33.063 に答える