trjhtr

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.