2618. 游戏

单点时限: 2.0 sec

内存限制: 256 MB

最近 Pollux 迷恋上了八数码游戏,相信大家对这个游戏并不陌生,小时候应该都玩过这个游戏吧。规则很简单,假如上图为原始状态,那么移动上图中的空格一步后的状态可以分别表示为下图的四个状态:

( Hint:上图分别为原图执行 up,right,down,left 后的最终状态)

在玩了很久之后,Pollux 逐渐发现这个游戏没有什么挑战。所以自己新发明了一种玩法,这种玩法需要两个人,所以 Pollux 便拉上 Castor 一起玩,规则如下 (假如 Pollux 为玩游戏的一方):

1、Pollux 先记住把数码的初始状态,然后蒙上眼睛。

2、Castor 给出 N 个移动步骤,每一步分别为 up,right,down,left 四个中的一个,Pollux 在脑袋中模拟出移动后的状态,并记住。

3、N 步以后 Pollux 说出数码的最终状态。

是不是很简单呢?现在 Pollux 决定推广这种玩法,鉴于这种游戏是锻炼记忆力的游戏,所以 Pollux 还在 YY 以后这个游戏会流行起来,所以事先请你帮忙写一个程序模拟这个过程。

输入格式

第一行为一个整数 T, 表示测数数据的组数 .

对于每组测试数据:

一开始有三行,每行三个数,每两个数之间用空格隔开,每个数分别为 (0-8) 的一个数字,其中 0 表示空格所在的位置,数据保证 0-8 每个数字只出现一次

然后一个整数 N( 0 <= N <= 10000 ) 表示移动的步数。

接下来 N 行,每行一个字符串 S,分别为上述四个之一,输入可能会让空格移动到外面,对于这种步骤,应该忽略

输出格式

对于每组数据,输出数码的最终的状态。

三行,每行三个数字之间间隔一个空格 . 第三个数字后面没有空格 .

每两组数据之间输出一个空行,不要在最后输出空行。

样例

Input
2
1 2 3
5 0 6
4 7 8
4
left
right
up
down
5 6 1
3 2 4
0 7 8
2
right
right
Output
1 2 3
5 0 6
4 7 8
5 6 1
3 2 4
7 8 0

70 人解决,125 人已尝试。

79 份提交通过,共有 306 份提交。

4.7 EMB 奖励。

创建: 11 年,4 月前.

修改: 3 年,1 月前.

最后提交: 8 月前.

来源: 华东师范大学2009校赛

题目标签