Question

i want a program in java that finds the shortest path in a 2D array with obstacles from source to destination

using BFS and recursion. The path must be stored in a queue.

The possible moves are left,right,up and down.

Answer 1

#Using BFS:

// Java program to find the shortest
// path between a given source cell
// to a destination cell.
import java.util.*;

class example
{
static int ROW = 9;
static int COL = 10;

// To store matrix cell cordinates
static class Point
{
   int x;
   int y;

   public Point(int x, int y)
   {
       this.x = x;
       this.y = y;
   }
};

// A Data Structure for queue used in BFS
static class queueNode
{
   Point pt; // The cordinates of a cell
   int dist; // cell's distance of from the source

   public queueNode(Point pt, int dist)
   {
       this.pt = pt;
       this.dist = dist;
   }
};

// check whether given cell (row, col)
// is a valid cell or not.
static boolean isValid(int row, int col)
{
   // return true if row number and
   // column number is in range
   return (row >= 0) && (row < ROW) &&
       (col >= 0) && (col < COL);
}

// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
static int rowNum[] = {-1, 0, 0, 1};
static int colNum[] = {0, -1, 1, 0};

// function to find the shortest path between
// a given source cell to a destination cell.
static int BFS(int mat[][], Point src,
                           Point dest)
{
   // check source and destination cell
   // of the matrix have value 1
   if (mat[src.x][src.y] != 1 ||
       mat[dest.x][dest.y] != 1)
       return -1;

   boolean [][]visited = new boolean[ROW][COL];
  
   // Mark the source cell as visited
   visited[src.x][src.y] = true;

   // Create a queue for BFS
   Queue<queueNode> q = new LinkedList<>();
  
   // Distance of source cell is 0
   queueNode s = new queueNode(src, 0);
   q.add(s); // Enqueue source cell

   // Do a BFS starting from source cell
   while (!q.isEmpty())
   {
       queueNode curr = q.peek();
       Point pt = curr.pt;

       // If we have reached the destination cell,
       // we are done
       if (pt.x == dest.x && pt.y == dest.y)
           return curr.dist;

       // Otherwise dequeue the front cell
       // in the queue and enqueue
       // its adjacent cells
       q.remove();

       for (int i = 0; i < 4; i++)
       {
           int row = pt.x + rowNum[i];
           int col = pt.y + colNum[i];
          
           // if adjacent cell is valid, has path
           // and not visited yet, enqueue it.
           if (isValid(row, col) &&
                   mat[row][col] == 1 &&
                   !visited[row][col])
           {
               // mark cell as visited and enqueue it
               visited[row][col] = true;
               queueNode Adjcell = new queueNode(new Point(row, col),
                                                   curr.dist + 1 );
               q.add(Adjcell);
           }
       }
   }

   // Return -1 if destination cannot be reached
   return -1;
}

// Driver Code
public static void main(String[] args)
{
   int mat[][] = {{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
               { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
               { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
               { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
               { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
               { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
               { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
               { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
               { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};

   Point source = new Point(0, 0);
   Point dest = new Point(3, 4);

   int dist = BFS(mat, source, dest);

   if (dist != Integer.MAX_VALUE)
       System.out.println("Shortest Path is " + dist);
   else
       System.out.println("Shortest Path doesn't exist");
   }
}

#Using Recursion:

class Main
{
   // M x N matrix
   private static final int M = 10;
   private static final int N = 10;

   // Check if it is possible to go to (x, y) from current position. The
   // function returns false if the cell has value 0 or already visited
   private static boolean isSafe(int mat[][], int visited[][], int x, int y)
   {
       return !(mat[x][y] == 0 || visited[x][y] != 0);
   }

   // if not a valid position, return false
   private static boolean isValid(int x, int y)
   {
       return (x < M && y < N && x >= 0 && y >= 0);
   }

   // Find Shortest Possible Route in a Matrix mat from source cell (0, 0)
   // to destination cell (x, y)

   // 'min_dist' stores length of longest path from source to destination
   // found so far and 'dist' maintains length of path from source cell to
   // the current cell (i, j)

   public static int findShortestPath(int mat[][], int visited[][],
                   int i, int j, int x, int y, int min_dist, int dist)
   {
       // if destination is found, update min_dist
       if (i == x && j == y)
       {
           return Integer.min(dist, min_dist);
       }

       // set (i, j) cell as visited
       visited[i][j] = 1;

       // go to bottom cell
       if (isValid(i + 1, j) && isSafe(mat, visited, i + 1, j)) {
           min_dist = findShortestPath(mat, visited, i + 1, j, x, y,
                                       min_dist, dist + 1);
       }

       // go to right cell
       if (isValid(i, j + 1) && isSafe(mat, visited, i, j + 1)) {
           min_dist = findShortestPath(mat, visited, i, j + 1, x, y,
                                       min_dist, dist + 1);
       }

       // go to top cell
       if (isValid(i - 1, j) && isSafe(mat, visited, i - 1, j)) {
           min_dist = findShortestPath(mat, visited, i - 1, j, x, y,
                                       min_dist, dist + 1);
       }

       // go to left cell
       if (isValid(i, j - 1) && isSafe(mat, visited, i, j - 1)) {
           min_dist = findShortestPath(mat, visited, i, j - 1, x, y,
                                       min_dist, dist + 1);
       }

       // Backtrack - Remove (i, j) from visited matrix
       visited[i][j] = 0;

       return min_dist;
   }

   public static void main(String[] args)
   {
       int mat[][] =
       {
               { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
               { 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 },
               { 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 },
               { 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 },
               { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
               { 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 },
               { 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 },
               { 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
               { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
               { 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 },
       };

       // construct a matrix to keep track of visited cells
       int[][] visited = new int[M][N];

       int min_dist = findShortestPath(mat, visited, 0, 0, 7, 5,
                                       Integer.MAX_VALUE, 0);

       if (min_dist != Integer.MAX_VALUE) {
           System.out.println("The shortest path from source to destination "
                           + "has length " + min_dist);
       }
       else {
           System.out.println("Destination can't be reached from source");
       }
   }
}