Rat in a Maze Problem 中的运行时错误 - I GFG

Question

enter image description here我遇到迷宫老鼠问题的运行时错误。你能告诉我哪里错了吗？

问题：

考虑将一只老鼠放在 N * N 阶方阵中的 (0, 0) 处。它必须到达 (N - 1, N - 1) 处的目的地。找出老鼠从源头到目的地可能采取的所有路径。老鼠可以移动的方向是 'U'（上）、'D'（下）、'L'（左）和 'R'（右）。矩阵中某个单元格的值为 0 表示它被阻塞，老鼠无法移动到它，而矩阵中某个单元格的值为 1 表示老鼠可以穿过它。注意：在一条路径中，不能多次访问任何单元格。如果源单元格为 0，则老鼠不能移动到任何其他单元格。

代码：

class Solution:
    def findPath(self, m, n):
        # code here
        if m[0][0]==0 or m[n-1][n-1]==0:
            return []
        list_of_ans=[]
        vis=[]
        ans=''
        vis=[[0 for _ in range(n)]for _ in range(n)]
        list_of_ans=self.search(n,m,ans,0,0,list_of_ans,vis)
        list_of_ans.sort()
        return list_of_ans  
    
    def search(self,n,m,ans,i,j,list_of_ans,vis):
        if i==n-1 and j==n-1:
            list_of_ans.append(ans)
            return list_of_ans
    
        if vis[i][j+1]==0 and j+1<n and m[i][j+1]==1:
            vis[i][j+1]=1
            ans += 'R'
            list_of_ans=self.search(n,m,ans,i,j+1,list_of_ans,vis)
            vis[i][j+1]=0


        if vis[i-1][j]==0 and i-1>-1 and m[i-1][j]==1:
            vis[i-1][j]=1
            ans+='U'
            list_of_ans=self.search(n,m,ans,i-1,j,list_of_ans,vis)
            vis[i-1][j]=0


        if vis[i][j-1]==0 and j-1>-1 and m[i][j-1]==1:
            vis[i][j-1]=1
            ans+='L'
            list_of_ans=self.search(n,m,ans,i,j-1,list_of_ans,vis)
            vis[i][j-1]=0


        if vis[i+1][j]==0 and i+1<n and m[i+1][j]==1:
            vis[i+1][j]=1
            ans+='D'
            list_of_ans=self.search(n,m,ans,i+1,j,list_of_ans,vis)
            vis[i+1][j]=0
        return list_of_ans

输入：

N = 4
m[][] = {{1, 0, 0, 0},
         {1, 1, 0, 1}, 
         {1, 1, 0, 0},
         {0, 1, 1, 1}}

错误：

Traceback (most recent call last):
  File "/home/e06cd8a4132efe0b88133e02abde22fd.py", line 70, in <module>
    result = ob.findPath(matrix, n[0])
  File "/home/e06cd8a4132efe0b88133e02abde22fd.py", line 12, in findPath
    list_of_ans=self.search(n,m,ans,0,0,list_of_ans,vis)
  File "/home/e06cd8a4132efe0b88133e02abde22fd.py", line 47, in search
    list_of_ans=self.search(n,m,ans,i+1,j,list_of_ans,vis)
  File "/home/e06cd8a4132efe0b88133e02abde22fd.py", line 26, in search
    list_of_ans=self.s.................

Answer 1

if vis[i][j+1]==0 and j+1<n and m[i][j+1]==1:

这可能会导致错误，因为它会在检查 j+1<n 之前计算 vis[i][j+1]==0。因此，如果 j 等于 n，则在检查 j+1 是否有效之前，第一次检查将导致错误。

要解决此问题，只需更改条件的顺序即可。您需要对所有 if 语句进行类似的更改。

Rat in a Maze Problem 中的运行时错误 - I GFG

Runtime error in Rat in a Maze Problem - I GFG

python

algorithm

graph-theory

backtracking