# Bidirectional BFS on a matrix in Python 2.7

This code is a bidirectional BFS search. Given any two points in a matrix having 0's and 1's, I would like to find if there exists a path between them. Also note that it is forbidden to enter a cell that has a value of 0.

One note I would like to make about the code is that I have maintained a duplicate matrix to check if a particular cell has been visited by the source/destination.

Can someone please let me know if there are any discrepancies in what I have implemented and how I can improve the time efficiency of this? I am new to Python.

import copy

def path_exists(grid, queries):
#iterate through queries.
result=[]
for (x1,y1,x2,y2) in queries:
print "query",x1,y1,x2,y2
if isValidIndex((x1,y1),(x2,y2),grid) != 0:
result.append(findPath(x1,y1,x2,y2,grid))
else:
result.append(0)

return result

def isValidIndex(startIndex,endIndex,grid):
if startIndex[0] >= len(grid) or startIndex[0] < 0 or startIndex[1] >= len(grid[0]) or startIndex[1] < 0 or endIndex[0] >= len(grid) or endIndex[0] < 0 or endIndex[1] >= len(grid[0]) or endIndex[1] < 0 :
return 0
return 1

def findPath(x1,y1,x2,y2,grid):
queue1=[[x1,y1]]
queue2=[[x2,y2]]

bool_grid = copy.deepcopy(grid)

source_path = 0
dest_path = 0

while(1):
if len(queue1) > 0:
if find_path_from_source(queue1,grid,bool_grid,3) == 1:
return 1

if len(queue2) > 0:
if find_path_from_source(queue2,grid,bool_grid,4) == 1:
return 1

if len(queue1) == 0 and len(queue2) == 0:
return 0

def find_path_from_source(queue,grid,bool_grid,val):
x=queue[0][0]
y=queue[0][1]
other_val = val

if val == 3:
other_val = 4
else:
other_val = 3

if x + 1 < len(grid):
if bool_grid[x+1][y] == other_val:
return 1
elif bool_grid[x+1][y] == 1:
bool_grid[x+1][y] = val
queue.append([x+1,y])

if y + 1 < len(grid[0]):
if bool_grid[x][y+1] == other_val:
return 1
elif bool_grid[x][y+1] == 1:
bool_grid[x][y+1] = val
queue.append([x,y+1])

if x - 1 >= 0:
if bool_grid[x - 1][y] == other_val:
return 1
elif bool_grid[x - 1][y] == 1:
bool_grid[x - 1][y] = val
queue.append([x - 1 , y])

if y - 1 >= 0:
if bool_grid[x][y - 1] == other_val:
return 1
elif bool_grid[x][y - 1] == 1:
bool_grid[x][y - 1] = val
queue.append([x, y - 1])

queue.pop(0)

grid =  [[1,0,0,1,1],
[0,1,1,1,1],
[1,1,0,1,1],
[0,1,1,0,1],
[1,1,1,0,1]]

queries=((1,2,2,3),(0,0,1,1),(2,0,0,4),(5,0,2,5),(4,4,0,0),(0,4,4,4))

x = path_exists(grid,queries)

print x


• isValidIndex handling two "indices" seems wrong. At least the condition you spell becomes too long. Besides, the condition looks somewhat inside-out. Consider

def isValidIndex(index, grid):
return 0 <= index[0] < len(grid) and 0 <= index[1] < len(grid[0])


That said, AFNP principle tells that you don't really need this function at all:

    for (x1,y1,x2,y2) in queries:
try:
result.append(findPath(x1,y1,x2,y2,grid))
except IndexError:
results.append(0)

• find_path_from_source has an execution path which returns nothing. Here you can get away with it, but the practice is in generally dangerous and indicates sloppy coding.

• The repetitive code in find_path_from_source should be wrapped in the loop:

    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
try:
if bool_grid[x + dx][y + dy] == other_val:
return 1
if bool_grid[x + dx][y + dy] == 1:
bool_grid[x + dx][y + dy] = val
queue.append([x + dx, y + dy])
except IndexError:
pass

• The bool_grid name is misleading. What is bool about it?

• Copying a large grid may hurt the performance. An alternative is to compare visited cells: once they have a common element, the path is found. Implementing them as sets may make it quite fast. Of course, when in doubt, profile.

• wouldnt the exception handling be slower than prechecking for conditions ? – Sujith Apr 18 '18 at 19:11
• @Sujith In languages like C++ and Java exceptions are heavy, and are only used as the last resort. Not in Python. Python is designed around lightweight exceptions (in fact, even the simple things like for loop use them under the hood). – vnp Apr 18 '18 at 22:36