使用python查找位置的短路径

Question

Guys this is a question i got part of google foobar challege You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left (0,0)(0,0) and the door into an escape pod is at the bottom right (w−1,h−1)(w−1,h−1).

Write a function answer(map) that generates the length of the shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed.

Test cases

Input:

maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]] Output:

7 Input:

maze = [[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]] Output:

11 and this is its answer i got online

from collections import deque

class Node:

    def __init__(self, x, y, saldo, grid):
        self.x = x
        self.y = y;
        self.saldo = saldo
        self.grid = grid

    def __hash__(self):
        return self.x ^ self.y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y and self.saldo == other.saldo

    def get_neighbors(self):
        neighbors = []
        x = self.x
        y = self.y
        saldo = self.saldo
        grid = self.grid
        rows = len(grid)
        columns = len(grid[0])

        if x > 0:
            wall = grid[y][x - 1] == 1
            if wall:
                if saldo > 0:
                    neighbors.append(Node(x - 1, y, saldo - 1, grid))
            else:
                neighbors.append(Node(x - 1, y, saldo, grid))

        if x < columns - 1:
            wall = grid[y][x + 1] == 1
            if wall:
                if saldo > 0:
                    neighbors.append(Node(x + 1, y, saldo - 1, grid))
            else:
                neighbors.append(Node(x + 1, y, saldo, grid))

        if y > 0:
            wall = grid[y - 1][x] == 1
            if wall:
                if saldo > 0:
                    neighbors.append(Node(x, y - 1, saldo - 1, grid))
            else:
                neighbors.append(Node(x, y - 1, saldo, grid))

        if y < rows - 1:
            wall = grid[y + 1][x]
            if wall:
                if saldo > 0:
                    neighbors.append(Node(x, y + 1, saldo - 1, grid))
            else:
                neighbors.append(Node(x, y + 1, saldo, grid))

        return neighbors

def answer(maze):
    rows = len(maze)
    columns = len(maze[0])

    source = Node(0, 0, 1, maze)
    queue = deque([source])
    distance_map = {source: 1}

    while queue:
        current_node = queue.popleft()

        if current_node.x == columns - 1 and\
            current_node.y == rows - 1:
            return distance_map[current_node]

        for child_node in current_node.get_neighbors():
            if child_node not in distance_map.keys():
                distance_map[child_node] = distance_map[current_node] + 1
                queue.append(child_node)

and this description was there along with solution Basically you need a breadth-first search with a minor tweak:

each node represents a cell in the grid (x- and y-coordinates), each
node knows its "saldo" (how many walls it may penetrate). What comes
to that saldo, if a node has zero saldo, it may not generate those its
neighbors that are occupied by wall. If saldo is s>0s>0, and the node
has a wall neighbor node uu, uu is generated with saldo s−1s−1.

The rest is breadth-first search: as soon you remove the exit node
from the queue, just print its distance from the starting node:

But even after a long effort i am unable to understand what "saldo"

means here and how it affects the result

我没有理解它的使用逻辑

Answer 1

you are allowed to remove one wall as part of your remodeling plans.

显然，变量saldo表示在越狱期间可以移除的墙的数量。
当您移除墙时，它会递减；会进行测试以确定是否仍允许您移除墙。你知道吗