Description

Sokoban (倉庫番, Sōko-ban, “warehouse keeper”) is a puzzle video game genre in which the player pushes crates or boxes around in a warehouse, trying to get them to storage locations.

• The player may move horizontally or vertically onto empty squares (never through walls or boxes).
• The player can move a box by walking up to it and push it to the square beyond. Boxes cannot be pulled, and they cannot be pushed to squares with walls or other boxes.

- From Wikipedia, the free encyclopedia.

 

Your goal is to find the actions required to solve the problem.

---

The possible tiles are listed as follows:

'o': The player stepping on a regular tile

'O': The player stepping on a target tile

'x': A box on a regular tile

'X': A box on a target tile

' ': Nothing on a regular tile

'.': Nothing on a target tile

'#': Wall

 

Your program should output a sequence of actions that push all the boxes to the target tiles, where the actions are represented by the uppercase WASD characters:

• W: move the player up
• A: move the player left
• S: move the player down
• D: move the player right

 

Example 1:

Input:

1
4 9
#########
#  xox..#
#   #####
#########

Output:

DDAAASAAWDDDD

• Your solution is not required to have the least number of moves. Any sequence that solves the problem is valid.
• Your program only needs to deal with valid inputs. It is guaranteed that:
  • there is only one player, stepping on either a regular tile or a target tile;
  • the number of target tiles is equal to the number of boxes;
  • all tiles other than wall tiles are within an enclosed area formed by wall tiles;
  • no more than 5 boxes;
  • there is at least one solution.
• If you get Runtime Error, maybe you should use a more efficient state representation to reduce memory usage.

---

 

Input

The first line contains a single integer T (1 ≤ T ≤ 100). Then T test cases follow.

For each test case:

• the first line gives two integers N and M (1 ≤ N*M ≤ 256);
• each of the next N lines consists of M characters, representing the tiles of each row.

Output

For each test, output a sequence of actions, represented by the uppercase WASD characters, that push all the boxes to the target tiles. Remember to add a '\n' at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss