问题描述

几乎每个人都知道一个名为“劳埃德十五拼图”（Lloyd fifteen puzzle）的流行游戏。这个拼图由十五个编号的方块组成，放置在一个$4×4$的方框中，其中一个位置是空的。游戏的目标是通过将相邻的方块移动到空位来排列方块。最终，方块应按数字顺序排列，数字$1$的方块位于左上角，接下来的方块按行优先顺序排列，最后一个位置（右下角）为空。

此外，KOKODáKH包含了这个游戏的变种。这个游戏是为高级玩家设计的，因此十五个方块可能太少。我们的游戏可以有任意大小的网格。你的任务是编写一个程序来模拟这个游戏的工作方式。对于给定的初始状态，程序需要重放一系列有效的移动，并显示拼图的最终状态。有效的移动是指将方块移动到相邻的空位（上、下、左、右）。任何其他移动都是无效的。

输入

输入由$Z$个任务组成。任务的数量由输入的第一行的一个正整数$Z$给出。任务描述如下。每个任务包括拼图的初始状态描述和需要执行的移动列表。

在拼图初始状态描述的第一行，有两个整数$R$和$S（2 ≤ R, S ≤ 1000）$，用空格分隔。$R$是行数，$S$是列数。接下来的$R$行描述拼图的行。每行有$S$个整数，整数之间用至少一个、最多十个空格分隔。行的开头可能有多达十个空格，这些空格应被忽略。行的末尾没有空格。每行的第一个数字对应于拼图的左上角。所有数字都在$0$到$R×S-1$之间（包括0和R×S-1），每个数字只出现一次。数字$0$只出现一次，表示空位的位置。

移动列表紧随其后。移动列表可能为空。每个移动单独占一行，由一个数字T（0 < T ≤ R×S-1）组成，表示需要移动的方块编号。移动列表的末尾是一个数字0。数字0表示输入结束，不是移动列表的一部分。

输出

对于每个任务，程序首先输出一行$“Skladacka cislo C:”$（拼图编号$C$），其中$C$替换为任务的编号。任务编号从$1$开始递增。

对于移动列表中的每个移动，程序判断移动是否有效。如果空位与方块T相邻，则移动有效。对于每个有效移动，程序在单独的一行输出：$“Kamen T presunut KAM.”$（方块T移动到KAM），其中$T$是方块编号，$KAM$是以下字符串之一：“doprava”（右）、“doleva”（左）、“nahoru”（上）或“dolu”（下）。如果移动无效，程序输出：“Neplatny tah kamenem T.”（方块T的移动无效）。

当移动列表结束后，程序以与输入类似的格式输出拼图的最终状态。输出应包括$R$行，每行包含$S$个数字。与输入格式的唯一区别是数字之间用恰好一个空格分隔。在每个任务之后（包括最后一个任务），程序输出一个空行。空行仅由换行符组成。

输入示例 1

2
4 4
 1  2  3  4
 5  6  7  8 
 9 10 11 12
13 14 15  0
15
11
7
0
4 4
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14  0 15
1
0

输出示例 1

Skladacka cislo 1:
Kamen 15 presunut doprava.
Kamen 11 presunut dolu.
Kamen 7 presunut dolu.
1 2 3 4
5 6 0 8
9 10 7 12
13 14 11 15
 
Skladacka cislo 2:
Neplatny tah kamenem 1.
1 2 3 4
5 6 7 8
9 10 11 12
13 14 0 15

来源

CTU Open 1999