RoAlgo Contest #5 - Back to School Edition | bloxorz

You might be familiar with the game Bloxorz. If not, please watch stage 1 of this video to understand the mechanics of the game. In this problem, there are no buttons, no possibility of splitting the player into two cubes, or any other features that do not appear in stage 1 of the video.

The player is a rectangular parallelepiped with dimensions $2 \times 1 \times 1$. Initially, its height is $2$ while its length and width are $1$. To move on the map, the player will rotate in four directions (North, South, East, West). With each rotation, the player's height, length, and width will interchange. For example, from the player's initial state, it can change to a height of $1$, a length of $2$, and a width of $1$.

Task

You are given a two-dimensional map that contains platforms at some positions. The player is allowed to move only on platforms. Check if it is possible for the player to move from an initial platform to a final platform, ending with a height of $2$ and a length and width of $1$. If it is possible, display a correct path that the player can use.

Input data

The first line contains the numbers $N$ and $M$, representing the dimensions of the map (number of rows and number of columns, respectively).

The next $N$ lines contain $M$ characters, each representing a piece of the map. The characters can be:

• _ — This character represents a platform.
• # — This character represents a space with nothing. The player is not allowed to move there.
• A — This character represents the initial platform.
• B — This character represents the final platform.

Output data

If there is no path, print NU.
If there is a path, print on the first line DA, and on the second line a sequence of characters from the set $\{$N$,$ S$,$ E$,$ V$\}$ representing the directions the player will take at each step (N — North, S — South, E — East, V — West).

Constraints and clarifications

• $1 \leq N,M \leq 2\ 000$
• The player must be entirely on platforms. It is not allowed for half of the player to be on a platform while the other half is not.
• The problem does not necessarily require the path to have the minimum number of steps.
• There are no platforms outside the map.
• You will receive $40\%$ of the points for a subtask for correctly displaying only the first message (DA/NU).

Example

stdin

6 10
___#######
_A____####
_________#
#_________
#####__B__
######___#

stdout

DA
EESEEES

Explanation

The example is the same as in the video, as well as the moves made.

The solutions ESSEESE or EESENVSEEESSNVNSVNESEVSSVENVNEESVNESVNESV are also correct.