finding shorted path to a position using python -

guys question got part of google foobar challege have maps of parts of space station, each starting @ prison exit , ending @ door escape pod. map represented matrix of 0s , 1s, 0s passable space , 1s impassable walls. door out of prison @ top left (0,0)(0,0) , door escape pod @ bottom right (w−1,h−1)(w−1,h−1).

write function answer(map) generates length of shortest path prison door escape pod, allowed remove 1 wall part of remodeling plans. path length total number of nodes pass through, counting both entrance , exit nodes. starting , ending positions passable (0). map solvable, though may or may not need remove wall. height , width of map can 2 20. moves can made in cardinal directions; no diagonal moves 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 , answer 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 , self.y == other.y , 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]          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 description there along solution need breadth-first search minor tweak:

each node represents cell in grid (x- , y-coordinates), each
node knows "saldo" (how many walls may penetrate). comes
saldo, if node has 0 saldo, may not generate its
neighbors occupied wall. if saldo s>0s>0, , node
has wall neighbor node uu, uu generated saldo s−1s−1.

the rest breadth-first search: remove exit node
queue, print distance starting node:

but after long effort unable understand "saldo"

means here , how affects result

i did not undertand logic of use

you allowed remove 1 wall part of remodeling plans.

apparently, variable saldo represents number of walls can remove during escape.
decremented when remove wall; tests made assert whether still allowed remove wall.