Java 2D array shortest path from point A to point B with obstacles

Question

Objective: Finding the least amount of movement required to reach destination.

Scenario: in a 2D Array 8*8 with elements such as the following:

*......B
........
****.**.
.A....*.
........
....**..
........
....*...

where

• " A " represents the starting point.
• " B " represents the destination point.
• " * " represents an obstacle.
• " . " represents an empty cell.

Currently I have done the following code:

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

class main
{
    public static void main(String args[]) throws FileNotFoundException,IOException
    {   
        FileInputStream FS = new FileInputStream("path.in");
        DataInputStream DS = new DataInputStream(FS);
        BufferedReader buffer = new BufferedReader(new InputStreamReader(DS));

        String strLine = buffer.readLine();             
        int testCase = Integer.parseInt(strLine);

        int R,C;

        for(int i = 0;i < testCase;i++)
        {           

            strLine = buffer.readLine();                    
            String input[] = strLine.split(" ");

            R = Integer.parseInt(input[0]);
            C = Integer.parseInt(input[1]);

            char[][] array = new char[R][C];

            int sCoordX = 0;
            int sCoordY = 0;
            int eCoordX = 0;
            int eCoordY = 0;

            for(int j = 0; j < R ; j++)
            {
                strLine = buffer.readLine();        

                for(int k = 0;k < C;k++)
                {                               
                    array[j][k] = strLine.charAt(k);
                    if(array[j][k] == 'A')
                    {
                        sCoordX = j;
                        sCoordY = k;
                    }

                    if(array[j][k] == 'B')
                    {
                        eCoordX = j;
                        eCoordY = k;
                    }
                }   
            }

            boolean reached = false;
            int counter = 0;
            int posX = sCoordX;
            int posY = sCoordY;
            while(!reached)
            {
                if(array[posX][posY] == 'B')
                {
                    reached = true;
                    System.out.println("You are in goal!");
                    System.out.println(array[posX][posY]);
                    System.out.println("Number of steps:"+counter);
                }

                if(!reached && posX > eCoordX)
                {
                        posX--;
                        counter++;                  
                }
                else if(!reached && posX < eCoordX)
                {
                    posX++;
                    counter++;                  
                }

                if(!reached && posY > eCoordY)
                {
                    posY--;
                    counter++;          
                }
                else if(!reached && posY < eCoordY)
                {
                    posY++;
                    counter++;              
                }
            }
        }   
    }
}

It does the job of finding the "shortest" amount of steps required to reach the destination however it will consider anything/obstacles as empty cells that it can move to.

I'm currently unable to figure out a way to code it in a way that will allow it to recognize a proper decision for the next movement.

I'm thinking of using array lists and some algorithm,however I tried reading some algorithms such as the Dijkstra's algorithm but it seemed really confusing,can anybody help me understand it in a very easy manner to implement it in java?

//-(sorry for my coding skills,I'm still a beginner)-

Answer 1

You don't need any special algorithm for this task, only a breadth-first search in a graph. Consider points that are reachable in 1 step as the first level of your graph, points thats are reachable in 2 steps(those ones are connected to any of the first level points, but not to the source point) as the second level, etc.

First visit the points which are directly reachable from the source point, then visit the second-level points, then visit the third-level points. You can achieve this by storing the nodes in a list. First you visit the source, and push the neighbouring nodes to the end of your list. Then you visit each node in your list, and push their neighbouring nodes to the end of the list, if they are not in the list so far. Once you reach the target node, you are done. You can store the level of each node, and also, you can store the preceding node, so you can find the path backwards from the target node.

One important thing to note: don't add obstacles to your list, this way there will be no routes crossing that point.