使用 Python 查找距离银行警卫的最短距离

pythonserver side programmingprogramming更新于 2025/9/27 5:00:17

假设我们有一个矩阵,其中有三个字母"O"、"G"和"W",其中"O"代表开放空间,"G"代表警卫,"W"代表银行的墙壁,我们必须根据它们与一个警卫的最短距离替换矩阵中的所有 O,否则我们就无法穿过任何墙壁。在输出矩阵中,警卫被替换为 0,墙壁被替换为 -1。

因此,如果输入如下

OOOOG
OOOWO
OWOOO
GWWWO
OOOOG

则输出将是

33210
233-11
1-1432
0-1-1-11
12210

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

  • M := 5

  • N := 5

  • dir_row := [-1, 0, 1, 0]

  • dir_col := [0, 1, 0, -1]

  • 定义一个函数 is_ok() 。这将需要 i, j

  • 如果 (i 在范围 0 和 M 内) 或 (j 在范围 0 和 j N 内),则

    • 返回 False

  • 返回 True

  • 定义一个函数 isSafe() 。这将需要 i、j、矩阵、结果

  • 如果矩阵[i, j]不是"O"或 result[i, j] 不为 -1,则

    • 返回 False

  • 返回 True

  • 定义一个函数 calculate_dist()。这将采用矩阵

  • result := 制作一个 M x N 阶矩阵并用 -1 填充

  • 定义一个双端队列 q

  • 对于 0 到 M 范围内的 i,执行

    • 对于 0 到 N 范围内的 j,执行

      • result[i, j] := -1

      • 如果 matrix[i, j] 与 'G' 相同,则

        • pos := [i, j, 0]

        • 在 q 的左侧插入 pos

        • result[i, j] := 0

  • while size of q > 0 非零,则执行

    • curr := 从 q 中删除最后一个元素

    • x, y, dist := curr[0], curr[1], curr[2]

    • 对于范围在 0 到 3 内的 i,则执行

      • 如果 is_ok(x + dir_row[i], y + dir_col[i]) 非零且 isSafe(x + dir_row[i], y + dir_col[i], matrix, result) 非零,则

        • result[x + dir_row[i], y + dir_col[i]] := dist + 1

        • pos := [x + dir_row[i], y + dir_col[i], dist + 1]

        • 在 q 的左侧插入 pos

  • 对于 0 到 M 范围内的 i,执行

    • 对于 0 到 N 范围内的 j,执行

      • 显示结果[i, j]

    • 转到下一行

示例

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

from collections import deque as queue
M = 5
N = 5
dir_row = [-1, 0, 1, 0]
dir_col = [0, 1, 0, -1]
def is_ok(i, j):
   if ((i < 0 or i > M - 1) or (j < 0 or j > N - 1)):
      return False
   return True
def isSafe(i, j,matrix, result):
   if (matrix[i][j] != 'O' or result[i][j] != -1):
      return False
   return True
def calculate_dist(matrix):
   result = [[ -1 for i in range(N)]for i in range(M)]
   q = queue()
   for i in range(M):
      for j in range(N):
         result[i][j] = -1
         if (matrix[i][j] == 'G'):
            pos = [i, j, 0]
            q.appendleft(pos)
            result[i][j] = 0
   while (len(q) > 0):
      curr = q.pop()
      x, y, dist = curr[0], curr[1], curr[2]
   for i in range(4):
      if is_ok(x + dir_row[i], y + dir_col[i]) and isSafe(x + dir_row[i], y + dir_col[i], matrix, result) : result[x + dir_row[i]][y + dir_col[i]] = dist + 1
      pos = [x + dir_row[i], y + dir_col[i], dist + 1]
      q.appendleft(pos)
   for i in range(M):
      for j in range(N):
         if result[i][j] > 0:
            print(result[i][j], end=" ")
         else:
            print(result[i][j],end=" ")
      print()

matrix = [['O', 'O', 'O', 'O', 'G'],
   ['O', 'O', 'O', 'W', 'O'],
   ['O', 'W', 'O', 'O', 'O'],
   ['G', 'W', 'W', 'W', 'O'],
   ['O', 'O', 'O', 'O', 'G']]

calculate_dist(matrix)

输入

[['O', 'O', 'O', 'O', 'G'],
['O', 'O', 'O', 'W', 'O'],
['O', 'W', 'O', 'O', 'O'],
['G', 'W', 'W', 'W', 'O'],
['O', 'O', 'O', 'O', 'G']]

输出

3 3 2 1 0
2 3 3 -1 1
1 -1 4 3 2
0 -1 -1 -1 1
1 2 2 1 0

相关文章


有用资源