Problem $4$

Given is an a xx b matrix where every cell corresponds to either an empty space or a wall.

This matrix represents a maze and in it are also two Things: Thing One and Thing Two.

The Things start at different empty spaces. And, somehow, they got synchronized: They do

exactly the same movements $-$ when Thing One goes west, so does Thing Two; when Thing

One goes east, so does Thing Two; and the same happens when they go south or north.

They move at the same time: For example, if Thing One is east of Thing Two and they

move east, both Things move. The Things cannot go to a location where there is an obstacle

$($or the other Thing, unless it is moving away$).$ For example, if there is an obstacle east of

Thing One but not of Thing Two, if they go east only Thing Two moves. Or$,$ if east of

Thing One there is an obstacle and west of it there is Thing Two, if they try to move east,

they will stay in their current locations as Thing One is blocked by the obstacle and Thing

Two by Thing One.

Things One and Two want to get out of the house, and they want to do so at the very

same time $($that is$,$ they want to leave the house with the same move$).$ The Things get out

of the house if they move north in row $1,$ south in row a$,$ west in column $1,$ or east in column

b$.$ This is proving to be very tricky. Please help them by designing an O$(($ab$)^(2))$ algorithm

that will tell them how to get out in the smallest number of moves $($or it will tell them that

the task is impossible$).$

For example, for the $3$xx$8$ input in the figure above, where dark entries represent walls

and the numbers the starting position of the respective Thing, they can get out in $6$ moves,

for example: east$-$north$-$east$-$south$-$north$-$north.

can only use java scanner, not java.utils