Question

Programming language is Java 8

Thank you

Things are tense on the battlefield and our army is on the verge of defeat. The only chance is to retreat for now, regroup, and then initiate another attack. To do this however, the king must be rescued first. A brave soldier named S wants to rescue the king. S wants to get to the king as fast as possible while avoiding the obstacles on the field such as pits, trees, bodies, etc. Find the length of the shortest path from S to the king. The battlefield is modeled as a two dimensional table. The objective is to know the minimum number of moves to get from cell S (position of the solider) to cell K (position of the king) on the table. In each move, S can either go right, left, up, or down one cell in the table. In particular, from a cell at row i and column j, S can only move to: (1) İ + 1 and j, or (2) i-1 and j, or (3) i and j + 1, or (4) ị and J-1, given that the cell S goes to does not have an obstacle and is not out of the table boundaries. Input Format The first line of the input contains a positive integer n In the next n lines, the battlefield is described as an n x n table. There are n lines where each line has n characters. Each character is one of the following: 1)A cell represents a cell that S can move to without any problem 2) A'x cell represents a cell with some obstacle on it that cannot be used. 3) 'S' shows the location of S 4) 'K' shows the location of the king Constraints 1 < n 〈 1000. There is exactly one 'S' cell and one 'K' cell in the input. Output Format

Answer 1

I have Solved the above problem in java, The solution works well for the above test cases. It is a basic use case of BFS algorithm. I have created a custom class called pair that stores the location of each point(co-ordinates) along with the distances travelled so far. I have also added relevant comments for you to understand.

SOLUTION:

import java.util.*;
import java.lang.*;
import java.io.*;
class Solution
{
   public static void main (String[] args) throws java.lang.Exception
   {
   Scanner sc = new Scanner(System.in);
       int n=sc.nextInt();
       char[][] ar= new char[n][n]; //input array
       boolean[][] visited=new boolean[n][n]; //visited array
       int pos_x=0,pos_y=0; //position of s
       int ans=-1;
       for(int i=0;i<n;i++){
       String s=sc.next(); //get next line
       for(int j=0;j<n;j++){
       ar[i][j]=s.charAt(j); //fill the array per character
       if(ar[i][j]=='S'){ //if character is Starting point
       pos_x=i; //initialize coordinates of S
       pos_y=j;
       }
       }
       }
       Queue<pair> q = new LinkedList<>(); //create queue
       q.add(new pair(pos_x,pos_y,0)); //add to queue
       while(!q.isEmpty()){
       pair p=q.remove(); //remove and make it visited true
       visited[p.x][p.y]=true;
       //System.out.println(p.x+" "+p.y+" "+p.ans);
       if(ar[p.x][p.y]=='K') { //if we have reached K(destination)
       ans=p.ans; //fetch the answer and break out
       break;
       }
       //Now adding all neighbours to the queue
       // check and move to (x-1,y)
       if(p.x-1>=0 && p.x-1<n && p.y>=0 && p.y<n && ar[p.x-1][p.y]!='X' && !visited[p.x-1][p.y])
       q.add(new pair(p.x-1,p.y,p.ans+1));
       // check and move to (x,y+1)
       if(p.x>=0 && p.x<n && p.y+1>=0 && p.y+1<n && ar[p.x][p.y+1]!='X' && !visited[p.x][p.y+1])
       q.add(new pair(p.x,p.y+1,p.ans+1));
       // check and move to (x+1,y)
       if(p.x+1>=0 && p.x+1<n && p.y>=0 && p.y<n && ar[p.x+1][p.y]!='X' && !visited[p.x+1][p.y])
       q.add(new pair(p.x+1,p.y,p.ans+1));
       // check and move to (x,y-1)
       if(p.x>=0 && p.x<n && p.y-1>=0 && p.y-1<n && ar[p.x][p.y-1]!='X' && !visited[p.x][p.y-1])
       q.add(new pair(p.x,p.y-1,p.ans+1));
       }
       //print the answer
       if(ans==-1)
       System.out.println("IMPOSSIBLE");
       else System.out.println(ans);
   }
//custom class pair that stores location of a the coordinates and the distance so far
public static class pair{
int x;
int y;
int ans;
pair(int a,int b,int answer){
x=a;y=b;ans=answer;
}
}
}