1 of 10

# BFS shortest path

I have the following code to return the shortest path on a matrix from top left corner to bottom right corner, with the option of removing one of wall cells (marked with '1') by changing its value to '0'. My approach is to make a list of removable walls and then by removing them one at a time in a loop, do a BFS search for the shortest path. At the end, I return the shortest path overall.

I have the following code that works. However, when I deal with larger matrices, it becomes very slow and I can't get passed the test code due to exceeding the time limit.

I was wondering if there is a problem in my algorithm or there would be a better approach to this problem.

Here is my code:

class Queue:
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

def enqueue(self, item):
self.items.insert(0,item)

def dequeue(self):
return self.items.pop()

def size(self):
return len(self.items)

neighbors = (
(point[0]-1, point[1]),
(point[0], point[1]-1),
(point[0], point[1]+1),
(point[0]+1, point[1]))

for p in neighbors:
if 0 <= p[0] < maze_dim[0] and 0 <= p[1] < maze_dim[1]:
yield p

def removable(maz, ii, jj):
counter = 0
for p in adjacent_to((len(maz),len(maz[0])), (ii, jj)):
if maz[p[0]][p[1]] == 0:
counter += 1

if counter >= 2:
return True
else:
return False

path_length = 0

if not maze:
return

dims = (len(maze), len(maze[0]))
end_point = (dims[0]-1, dims[1]-1)

# list of walls that can be removed
passable_walls = [0]
for i in xrange(dims[0]):
for j in xrange(dims[1]):
if maze[i][j] == 1 and removable(maze, i, j):
passable_walls.append((i, j))

shortest_path = 0
best_possible = dims[0] + dims[1] - 1

path_mat = [[None] * dims[1] for _ in xrange(dims[0])]  # tracker matrix for shortest path
path_mat[dims[0]-1][dims[1]-1] = 0  # set the starting point to destination (lower right corner)

for i in xrange(len(passable_walls)):

temp_maze = maze
if passable_walls[i] != 0:
temp_maze[passable_walls[i][0]][passable_walls[i][1]] = 0

stat_mat = [['-'] * dims[1] for _ in xrange(dims[0])]  # status of visited and non visited cells

q = Queue()
q.enqueue(end_point)

while not q.isEmpty():
curr = q.dequeue()

if curr == (0,0):
break

if temp_maze[next[0]][next[1]] == 0:  # Not a wall
temp = path_mat[curr[0]][curr[1]] + 1
if temp < path_mat[next[0]][next[1]] or path_mat[next[0]][next[1]] == None:  # there is a shorter path to this cell
path_mat[next[0]][next[1]] = temp
if stat_mat[next[0]][next[1]] != '+':  # Not visited yet
q.enqueue(next)

stat_mat[curr[0]][curr[1]] = '+'  # mark it as visited

if path_mat[0][0]+1 <= best_possible:
break

if shortest_path == 0 or path_mat[0][0]+1 < shortest_path:
shortest_path = path_mat[0][0]+1

return shortest_path

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]
]

# maze = [
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
# [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
# [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# ]

# maze = [
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
# [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
# [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# ]