python - 无法找到到达包括障碍物在内的目标的最短距离

Question

我试图找到到达我的目标 X 的最小可能距离。下面提供的是图表的快照。

O代表Occupied，V代表Vacant，X代表经理（我的目标）

以下是我找到最短距离的方法。但是在运行我的代码后我没有得到输出。

x=[['O','O','O','O','O','O','O','X'],
      ['O','V','O','O','O','O','O','O'],
      ['O','O','V','O','O','O','V','O'],
      ['O','O','O','O','O','O','O','O'],
      ['O','O','O','O','O','O','O','O'],
      ['O','O','O','O','O','O','O','O'],
      ['O','O','O','O','O','O','O','O'],
      ['O','O','O','O','V','O','O','O']]

from collections import deque
def solveMaze(maze):
        R, C = len(maze), len(maze[0])
    
        start = (0, 0)
        for r in range(R):
            for c in range(C):
                if maze[r][c] == 'V':
                    start = (r, c)
                    break
            else: continue
            break
        else:
            return None
    
        queue = deque()
        queue.appendleft((start[0], start[1], 0))
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        visited = [[False] * C for _ in range(R)]
    
        while len(queue) != 0:
            coord = queue.pop()
            visited[coord[0]][coord[1]] = True
    
            if maze[coord[0]][coord[1]] == "X":
                return coord[2]
    
            for dir in directions:
                nr, nc = coord[0]+dir[0], coord[1]+dir[1]
                if (nr < 0 or nr >= R or nc < 0 or nc >= C or maze[nr][nc] == "O" or visited[nr][nc]): continue
                queue.appendleft((nr, nc, coord[2]+1))
                
                print(solveMaze(x))

标签： python