在Bankin Python中找到与守卫的最短距离

假设我们有一个矩阵，其中填充了三个字母“ O”，“ G”和“ W”，其中“ O”代表开放空间，“ G”代表门卫，“ W”代表银行的墙，我们必须替换矩阵中所有O，因为它们与一个警卫的最短距离，我们不能穿过任何墙。在输出矩阵中，防护罩被替换为0，墙壁被替换为-1。

所以，如果输入像

那么输出将是

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

• M：= 5

• N：= 5

• dir_row：= [-1，0，1，0]

• dir_col：= [0，1，0，-1]

• 定义一个函数is_ok()。这需要我，j

• 如果（i在范围0和M之间）或（j在范围0和j N之间），则

• 返回False

• 返回True

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

• 如果matrix [i，j]不是'O'或result [i，j]不是-1，则

• 返回False

• 返回True

• 定义一个函数calculate_dist()。它将使用矩阵

• 结果：=制作一个M×N阶的矩阵并用-1填充

• 定义双头队列q

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

• 结果[i，j]：= -1

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

• pos：= [i，j，0]

• 在q的左侧插入pos

• 结果[i，j]：= 0

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

• 当q> 0的大小不为零时，执行

• 如果is_ok（x + dir_row [i]，y + dir_col [i]）为非零，而isSafe（x + dir_row [i]，y + dir_col [i]，矩阵，结果）为非零，则

• 结果[x + dir_row [i]，y + dir_col [i]]：= dist + 1

• pos：= [x + dir_row [i]，y + dir_col [i]，dist + 1]

• 在q的左侧插入pos

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

• x，y，dist：= curr [0]，curr [1]，curr [2]

• 对于0到3范围内的i，执行

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

• 显示结果[i，j]

• 对于0到N范围内的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