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] &gt;= len(grid) or startIndex[0] &lt; 0 or startIndex[1] &gt;= len(grid[0]) or startIndex[1] &lt; 0 or endIndex[0] &gt;= len(grid) or endIndex[0] &lt; 0 or endIndex[1] &gt;= len(grid[0]) or endIndex[1] &lt; 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) &gt; 0:
           if find_path_from_source(queue1,grid,bool_grid,3) == 1:
               return 1

       if len(queue2) &gt; 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 &lt; 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 &lt; 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 &gt;= 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 &gt;= 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 &lt;= index[0] &lt; len(grid) and 0 &lt;= index[1] &lt; 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.