程序查找到达Python右下角所需的最小单元数

假设我们有一个表示迷宫的2D网格，其中0表示空白，1表示墙。我们将从grid [0，0]开始，我们必须找到到达网格右下角所需的最小平方数。如果我们无法到达，则返回-1。

所以，如果输入像

那么输出将是5

为了解决这个问题，我们将遵循以下步骤-

• R：=网格的行数，C：=网格的列数

• q：= [0，0，1]，当A [0，0]为1时，否则为新列表

• A [0，0]：= 1

• 对于q中的每个(r,c,d)，执行

• 对于[[r + 1，c），（r − 1，c），（r，c +1），（r，c − 1）]中的每个[x，y]

• A [x，y]：= 1

• 在q的末尾插入（x，y，d + 1）

• 如果x在0到R的范围内，y在0到C的范围内，并且A [x，y]等于0，则

• 返回d

• 如果(r,c)与（R − 1，C − 1）相同，则

• 
  

• 返回-1

让我们看下面的实现以更好地理解-

示例

class Solution:
   def solve(self, A):
      R, C = len(A), len(A[0])
      q = [(0, 0, 1)] if not A[0][0] else []
      A[0][0] = 1
      for r, c, d in q:
         if (r, c) == (R − 1, C − 1):
            return d
         for x, y in [(r + 1, c), (r − 1, c), (r, c + 1), (r, c −1)]:
            if 0 <= x < R and 0 <= y < C and A[x][y] == 0:
               A[x][y] = 1
               q.append((x, y, d + 1))
      return −1
ob = Solution()grid = [
   [0, 0, 0],
   [1, 0, 0],
   [1, 0, 0]
]
print(ob.solve(grid))

输入值

grid = [ [0, 0, 0], [1, 0, 0], [1, 0, 0] ]

输出结果

5