Write a program in java:

The Problem:

Given the initial state of the $8$ by $8$ grid, showing the initial locations of the drones, the locations

each of the drones must deliver their food and the no$-$fly zone squares, determine the fewest

number of remote control button presses necessary to have all of the drones successfully deliver

their food. If this is impossible, determine that the task is not possible.

$1)$ The entire $8$ by $8$ grid is surrounded by no$-$fly zone squares $($not drawn in but just assumed to

be there.$)$

$2)$ Two drones may occupy the same grid square at the same time so long as it$$s not a no$-$fly zone

square.

$3)$ A drone treats each group$$s location except for the one it$$s delivering to as a no$-$fly zone. Therefore, a drone can not fly through another drone's dropoff location and treats it like a no$-$fly zone. For example, D$1$ cannot got through G$2.$

$4)$ The drones are controlled by one remote so they must move simultaneously. For example, when the down is pressed, all drones on the grid move down by one.

The Input:

The first line of input contains a single integer, n n representing the number of drones

for the input case. The corresponding drones are labeled D$1$ through Dn and the corresponding

groups to which they are delivering food are labeled G$1$ through Dn$.$

The following eight lines each contain $8$ space separated strings of two characters each,

representing that row of the input grid. If the two characters are $\_\_,$ the grid square is an open

square. If the characters start with $$D$,$ then that represents

drone's starting position. If the the character starts with $$G$,$ then that represents the destination drone is delivering food. Finally, if the two characters are $$XX$,$ that means the corresponding grid square is a no$-$fly zone. $($These are capital letter X$$s$.)$

The Output:

Output a single integer: $-1$ if it$$s impossible to get the drones to all make their delivering or a

positive integer representing the fewest number of remote control button pushes necessary to get

the drones to all make their deliveries.

Additionally, please use bitmasking to solve as described in this example:

The key information we need to know about the state is the location of each drone. Each drone has

a row number $(0$ to $7)$ and a column number $(0$ to $7).$ We can store a row number using three bits

and a column number using three bits. Thus, the position of one drone can be stored as a single

integer in between $0$ and $63,$ which takes up $6$ bits. If we have n drones, we can simply use a single

integer that has $6$n bits. Thus, if we have four drones, an integer which uses the $24$ least significant

bits $($in between $0$ and $224$

$-1)$ suffices to completely store the state of the board.

For example, for the first sample, the first drone is at row $1,$ column $4,$ which is equal to position

$1$ x $8+4=12,$ the second drone is at row $1,$ column $2($position $=1$ x $8+2=10),$ and the third

drone is at row $5,$ column $6($position $=5$ x $8+6=46).$ This means the integer storing the initial

position of the board is:

In binary, this number is:

$101110001010001100$

Drone $1$ is highlighted in purple, drone $2$ is highlighted in blue and drone $3$ is highlighted in yellow.

$($It$$s more natural to think about them as drone $0,$ drone $1$ and drone $2.)$ Notice that the bits in

purple, when split into groups of three convert to $(1,4),$ the bits in blue when split into $3$ convert

to $(1,2)$ and the bits in yellow when split into groups of $3$ convert to $(5,6).$ So$,$ the BFS then starts

at $$board position$189068$ for the first sample.

In the BFS$,$ for each possible board state $($integer$),$ we$$ll store the $$distance$,$ number of remote

control moves, from the initial position to that board state. Since we can make an array of size $224$

$,$

we$$ll store our distances in an array of size $26$n$,$ where n is the number of drones for the input case.

Thus, distance$[189068]=0$ in the beginning and distance$[$x$]=-1$ for all other values of x in the

beginning of the BFS for the first sample input. Eventually, the distance array will fill with values

$1,2,3,$ etc. When the final board position of is reached, the

BFS can return the corresponding shortest distance.Sample Input

Sample Output