在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和jN之间），则
返回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