Manipulating the Power Square

Rosalina finds Super Mario puzzling over the Power Square and gives him another hint on how to unlock its power. ”Keep swapping 0 with one of its neighbors! I’ll tell you which neighbor,” Rosalina says to Mario. Rosalina then gives Mario a sequence of directions on which neighbor to swap with 0.

Input is a description of of the Power Square, followed by a number of commands. The first line is the size of the Power Square n. You may assume n<=100. The second line contains the n2 values in the Power Square, separated by spaces. Values start from the top left corner and move from left to right, moving down one row to the leftmost position when a row is filled.
Following the Power Square description are a number of commands, with each command on a separate line. Each command begins with the name of the command, followed by any additional command parameters.
There will no more than 100 commands.

The command ”SHOW” causes the current state of the Power Square to be displayed in n × n
form (each row of n values on a single line, separated by spaces), followed by a blank line.
The command ”MOVE” is followed by one more more moves: ”up”, ”down”, ”left”, or ”right”.
Each move is executed as follows:
– For ”up”, swap 0 with its neighbor above.
– For ”left”, swap 0 with its left neighbor.
– For ”right”, swap 0 with its right neighbor.
– For ”down”, swap 0 with its neighbor below.
If move attempts to swap 0 with a non-existent neighbor, then output ”FAILED” on a single line and stop attempting the remaining moves. If the move succeeds, ”MOVED” is output on a single line. In either case, the state of the Power Square is changed to reflect the moves made.

3
8 7 6 5 4 3 2 1 0
SHOW
MOVE up
SHOW
3
8 7 6 5 4 3 2 1 0
SHOW
MOVE up right

8 7 6
5 4 3
2 1 0

MOVED
8 7 6
5 4 0
2 1 3

8 7 6
5 4 3
2 1 0

FAILED

HDU 2010-05 Programming Contest