Shortest path in a grid

Question

I have a two dimensional matrix like

A......... 
##....##..
.####...##
..........
.......###
B.........
####...### 
#...#.###.

Where '.' represents path and '#' represents wall.I have to find the shortest path possible from point A to point B.I am familiar with BFS algorithm and it seems like a reasonable algorithm for the problem. But I find it confusing to apply on the grid.Can anyone suggest implementation of BFS algorithm in this problem with some pseudo-codes ?

Answer 1

The BFS algorithms is basically:

1.Enqueue the source vertex and mark it visited.

2.While the Q is not empty repeat 3 and 4.

3. Perform deque and the for the dequed vertex x, do

4. For all adjacent vertices of x, that are not visited and mark them visited and enqueue them to the Q.

So thats the basic algorithm, if we go step by step its very easy to apply these steps to grid,the only thing that we should be careful is for a cell in a grid there are 8 neighbours possible, and we must check the boundary conditions before traversing the neighbours, to avoid array index out of bounds.

Say we are at position A(a,b) and we want to reach B(c,d). We follow the similar 4 steps but with some modification as follows:

1.Make a Q of 2-d points,(You can do that easily in languages like Java, by making a class of 2-d points and then Q of objects of that class)

2.Make a 2-d array visited of size of grid of type boolean, initialized to false.

3.Make a 2-d array distance of size of grid of type integer, that will be used for the distance.

Let size of grid be nxm

Now the pseudocode is as follows:

Enqueue A(a,b) to the Q

Mark dist[a][b] = 0 and visited[a][b] = true

while( Q is not empty )
{
 Point p = deque(Q)

 if( p matches B(c,d) )
 {
   print( Yes path is possible from A to B with distance[c][d] )
   return
 }
 else
 {
  //Now all we have to do is check all the possible neighbour cells according
  // to our current position in the grid
  // So we have to check all the 8 neighbour cells
   if(p.y < m - 1)
   {
    if( grid[p.x][p.y + 1] != '#' and visited[p.x][p.y + 1] == false )
    {
     enqueue (p.x,p.y + 1) to the Q // step s1
     distance[p.x][p.y + 1] = distance[p.x][p.y] + 1 // step s2
     visited[p.x][p.y + 1] = true // step s3
    }
   }
   if(p.x < n - 1)
   {
    if( grid[p.x + 1][p.y] != '#' and visited[p.x + 1][p.y] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x + 1,p.y)
    }
   }
   if(p.y > 0)
   {
    if( grid[p.x][p.y - 1] != '#' and visited[p.x][p.y - 1] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x,p.y - 1)
    }
   }
   if(p.x > 0)
   {
    if( grid[p.x - 1][p.y] != '#' and visited[p.x - 1][p.y] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x - 1,p.y)
    }
   }
   if(p.x > 0 and p.y > 0)
   {
    if( grid[p.x - 1][p.y - 1] != '#' and visited[p.x - 1][p.y - 1] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x - 1,p.y - 1)
    }
   }
   if(p.x > 0 and p.y < m-1)
   {
    if( grid[p.x - 1][p.y + 1] != '#' and visited[p.x - 1][p.y + 1] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x - 1,p.y + 1)
    }
   }
   if(p.x < n-1 and p.y > 0)
   {
    if( grid[p.x + 1][p.y - 1] != '#' and visited[p.x + 1][p.y - 1] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x + 1,p.y - 1)
    }
   }
   if(p.x < n-1 and p.y < m-1)
   {
    if( grid[p.x + 1][p.y + 1] != '#' and visited[p.x + 1][p.y + 1] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x + 1,p.y + 1)
    }
   }
 }     
}
print( the path is not possible )

Answer 2

Very basically, think of every dot (.) as a node, and every two dots that are neighbors should also have an edge between them*. This way you get a graph that has all possible places that the path can go through, and it only includes valid edges.

From there it's pretty easy to run BFS...

* If you are allowed to move diagonally, then those edges should also be added. This is already getting into what exactly is the definition of a "neighbor".