Описание проблемы приведено ниже:
Учитывая матрицу из M строк и N столбцов, 0 представляет пустое пространство, - 1 представляет препятствие, а 1 представляет целевые точки (имеется несколько целевых точек).
Для каждого пустого места, если вы хотите достичь целевой точки на кратчайшем расстоянии, отметьте направление первого шага.
При запуске вы должны отметить точку как 2 Если вы начинаете вниз, вы должны пометить точку как 3. Если вы начинаете влево, вы должны пометить точку как 4. Если вы начинаете направо, вы должны отметить точку как 5.
Приоритет направления вверх, вниз, влево и вправо от большого к маленькому, то есть, если вы можете достичь целевой точки с кратчайшим расстоянием от точки вверх или вниз, вы должны начать движение.
Возвращает матрицу после маркировки. 0
Я пытался написать решение в python, но всегда получал 'TypeError:' NoneType 'объект не повторяется'. На самом деле не знаю почему. Буду очень признателен за вашу помощь, если вы сможете указать на проблему!
Моя основная идея заключается в том, чтобы для каждой пустой ячейки найти ближайшую цель с помощью BFS. затем, указав эту пустую ячейку в качестве начала и ближайшую цель в качестве пункта назначения, я узнаю направление первого шага. Код может быть не таким кратким, спасибо за ваше время и усилия!
class Solution:
"""
@param grid: the input matrix
@return: the new matrix
"""
grid = None
def shortestPath(self, grid):
# BFS
self.grid = grid.copy()
m = len(grid)
n = len(grid[0]) if m > 0 else 0
res = [[None] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if grid[i][j] not in [-1, 1]:
tarx, tary, step = self.bfs(i, j)
res[i][j] = self.search(i, j, tarx, tary)
else:
res[i][j] = grid[i][j]
return res
def search(self, i, j, tarx, tary):
dic = {0: 2, 1: 3, 2: 4, 3: 5}
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
min_dist = float('inf')
direction = -1
for idx, d in enumerate(dirs):
x, y = i + d[0], j + d[1]
if x == tarx and y == tary:
return dic[idx]
if self.inside(x, y):
arr = [tarx, tary]
_, __, dist = self.bfs(x, y, arr)
if min_dist > dist:
min_dist = dist
direction = dic[idx]
return direction
def bfs(self, i, j, target = None):
m = len(self.grid)
n = len(self.grid[0]) if m > 0 else 0
visit = [[False] * n for _ in range(m)]
visit[i][j] = True
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
qu = [(i, j, 0)]
while len(qu) > 0:
ti, tj, step = qu[0][0], qu[0][1], qu[0][2]
qu.pop()
for d in dirs:
x, y = ti + d[0], tj + d[1]
if self.inside(x, y) and not visit[x][y]:
if not target:
if self.grid[x][y] == 1:
return x, y, step + 1
else:
tarx, tary = target[0], target[1]
if x == tarx and y == tary:
return x, y, step + 1
visit[x][y] = True
qu.append((x, y, step + 1))
def inside(self, x, y):
if 0 <= x < len(self.grid) and 0 <= y < len(self.grid[0]) and self.grid[x][y] != -1:
return True
return False
if __name__ == '__main__':
testcase = [[1,0,0],[0,0,0]]
ans = Solution().shortestPath(testcase)
print(ans)