The Pharaoh’s Curse

Most of the contestants managed to arrive at the Benelux Algorithm Programming Contest on time. All except those unfortunate souls who chose to use a cheap car navigation system. A couple of wrong turns led them completely off course, and now they have ended up all over the world.

Consider the case of contestant J.-P. B. (who has asked to remain anonymous). After driving for countless hours he found himself beneath three miles of water in the middle of the Atlantic Ocean. He was so focused on his navigation system that he failed to look outside until he noticed that the air was getting very moist. Fortunately for this contestant there was a spare submarine under his seat, which allowed him to escape this perilous situation.

Tragic as this story seems, it is not even the worst. Another contestant, whom we will simply call S, wisely decided to travel by train. Sadly, she still listened to the advice of her evil car navigation system, and this morning she took a southbound train instead of heading north. After some more bad directions she found herself locked inside a labyrinth, in the pyramid of the Egyptian pharaoh Sok-O-Ban. As any experienced adventurer knows, these ancient tombs are often riddled with traps and other mechanisms. Sok-O-Ban’s final resting place was no exception.

During his lifetime this pharaoh was known for his sadistic behavior, and he liked to give impossible challenges to random strangers. It is therefore no coincidence that the cavern where contestant S ended up was completely closed off, surrounded by solid rock on every side.

After looking around, our protagonist S managed to draw a map of the tomb. Fortunately she found no skeletons, mummies or spiked death traps. She did discover some buttons embedded in the floor tiles. If she could press them all at the same time, then the hidden exit would open. But as soon as she would release one of the buttons, the door would close again.

Besides the buttons, the walls and a few dusty floor tiles, there were also two sarcophagi filled with rocks. To accommodate the small stature of the ancient Egyptians, the sarcophagi were cubes with sides measuring 1 meter, the same size as the floor tiles. It seemed that these sarcophagi were the key to escaping: by pushing them onto the buttons the exit could be kept open. Only one small problem remained: the sarcophagi were far too heavy to move by hand and too large to climb over.

Fortunately for S, the pharaoh did not anticipate the portable sarcophagus transporter she had conveniently stashed in her backpack. Attaching this reusable system to her arms allowed her to effortlessly push a sarcophagus exactly one meter straight ahead. This corresponds nicely to the 1 meter steps S used when marking out the grid in her map.

On the first line of the input is a positive integer, the number of test cases. Then for each test case:

• A line containing two positive integers h, w ≤ 50, the height and width of the maze.

• h lines of w characters each, the map of the cavern our protagonist made, in which:

  • ‘#’ is a wall or otherwise impassible space.
  • ‘.’ is an empty space, of which there are at most 100.
  • ‘S’ is our protagonist.
  • ‘X’ is one of the heavy sarcophagi. There are at most two of these.
  • ‘B’ is a button.
  • ‘E’ is the exit. There is exactly one exit, on the edge of the map.

The edge of the map contains only walls and the exit.

For each test case:

• One line containing the minimum number of steps2 it will take S to escape the tomb, or the text “impossible” if she cannot escape.

2S always takes one meter steps along the grid lines, possibly pushing a sarcophagus.