【解決方法】左上から右下に到達するために、mxn行列ですべての可能なパスを見つける方法

[ad_1]

左上から右下に到達するまで、MxN マトリックス内のすべての可能なパスを見つけようとしています。
4 つの移動が可能です (上、下、右、左)。

Example 1:
Input: 
[[1,2,3],[4,5,6]]

Output:
1 2 3 6
1 2 5 6
1 4 5 6
1 4 5 2 3 6

Example 2:
Input:
[[1,2,3],
[4,5,6],
[7,8,9]]

Output:
1 2 3 6 9
1 2 3 6 5 8 9
1 2 3 6 5 4 7 8 9
1 2 5 6 9
1 2 5 8 9
1 2 5 4 7 8 9
1 4 5 6 9
1 4 5 8 9
1 4 5 2 3 6 9
1 4 7 8 9
1 4 7 5 6 9
1 4 7 8 5 2 3 6 9

I got the following error
[1] [1, 2] [1, 2, 3] Traceback (most recent call last):
  File "/home/me/test.py", line 47, in <module>
    printAllPath(mat,0,0,[])
  File "/home/me/test.py", line 31, in printAllPath
    printAllPath(matrix, i, j+1, result) 
  File "/home/me/test.py.py", line 31, in printAllPath
    printAllPath(matrix, i, j+1, result) 
  File "/home/me/test.py", line 31, in printAllPath
    printAllPath(matrix, i, j+1, result) 
  [Previous line repeated 995 more times]
  File "/home/me/test.py", line 4, in printAllPath
    rows = len(matrix)
RecursionError: maximum recursion depth exceeded while calling a Python object

私が試したこと:

Python
def printAllPath(matrix, i, j, result):

    # get rows and columns
    rows = len(matrix)
    columns = len(matrix[0])

    # Track visited cell
    visited = [[False]*columns for k in range(rows)]

    # Define a queue
    q = []
    q.append((i,j))
    # result.append(matrix[i][j])
    # visited[i][j] = True

    while q:
        x, y = q.pop()

        # Destination reached
        if x == rows-1 and y == columns-1:
            print(result.append(matrix[x][y]))

		# Condition
        if (x >= 0 and y >= 0 and x < rows  and y < columns and not visited[x][y]):
            q.append((x,y))
            result.append(matrix[x][y])
            visited[x][y] = True
            print(result, end=' ')

        # go to the right
        printAllPath(matrix, i, j+1, result) 

        # go to the down
        printAllPath(matrix, i+1, j, result)

        # go to the left
        printAllPath(matrix, i, j-1, result)

        # go to the up
        printAllPath(matrix, i-1, j, result)


# Example
mat = [[1,2,3],
        [4,5,6]]

printAllPath(mat,0,0,[])

解決策 1

コードを実行しても、それが正しいとは限りません。 :笑う:
開発プロセスは電子メールを書くことと考えてください。コンパイルが成功したということは、電子メールを適切な言語 (たとえば、ドイツ語ではなく英語) で作成したことを意味します。電子メールに送信したいメッセージが含まれていたわけではありません。

これで、開発の第 2 段階に入ります (実際には第 4 段階または第 5 段階ですが、後で前の段階に進みます): テストとデバッグです。

それが何をするのか、そしてそれがあなたが望んでいたものとどのように違うのかを見ることから始めてください。 これは、なぜそれを行っているのかについての情報を提供するため、重要です。 たとえば、プログラムがユーザーに数字を入力させることを目的としており、それを2倍にして答えを出力する場合、入力/出力が次のようになると:

Input   Expected output    Actual output
  1            2                 1
  2            4                 4
  3            6                 9
  4            8                16

次に、問題がそれを2倍にするビットにあることは明らかです-それ自体を加算したり、2倍したりするのではなく、それ自体を乗算して入力の2乗を返します。
それで、コードを見ることができ、それがここのどこかにあることは明らかです:

C#
int Double(int value)
   {
   return value * value;
   }

何がうまくいかないのかがわかったら、デバッガーを使用して原因を突き止めます。 メソッドの最初の行にブレークポイントを置き、アプリを実行します。 ブレークポイントに到達すると、デバッガーが停止し、制御がユーザーに渡されます。 コードを行ごとに実行し (「シングル ステップ」と呼ばれます)、必要に応じて変数の内容を確認 (または変更) できるようになりました (コードを変更して、必要に応じて再試行することもできます)。
デバッガーの使用方法がわからない場合は、ここから始めてください。 pdb — Python デバッガ — Python 3.11.2 ドキュメント[^]

コードを実行する前に、コードの各行が何をすべきかを考え、「ステップ オーバー」ボタンを使用して各行を順番に実行したときに実際に何をしたかを比較します。 それはあなたが期待したことをしましたか? その場合は、次の行に進みます。
そうでない場合、なぜですか? どう違うの?
うまくいけば、そのコードのどの部分に問題があり、何が問題なのかを突き止めるのに役立つはずです。
これはスキルであり、開発だけでなく現実の世界でも役立つため、開発する価値のあるスキルです。 そして、すべてのスキルと同様に、それは使用することによってのみ向上します!

[ad_2]

コメント

タイトルとURLをコピーしました