攻占黄金乡

时间限制:50s      空间限制:128MB

题目描述

 《海猫鸣泣之时》EP8终于在今年暑假的末尾出了汉化,作为整个作品中高人气人物古户绘梨花,自然也是在剧中大活跃。在攻占黄金乡的战役中担任了指挥官一职,而整个战役过程也都被记录在了图书之都中,方便后来人的复盘。
  当时的战况如下,黄金乡可以看做是一个长方体空间,我们用(0,0,0)~(n-1,m-1,k-1)表示里面的每一个单位区域,绘梨花指挥了t艘不同等级的战舰依靠魔法突然出现在了黄金乡的t个不同的区域,之后从战舰上便源源不断的涌出山羊们。每一个单位时刻,山羊们会从自己所在的区域向四周6个方向扩展一个区域(如果那个相邻的区域已经被占领了,就不扩展),如果两队山羊在同一时刻想占领同一区域,那么等级高的山羊优先占领。
  没过多久,黄金乡就变成了一片山羊海,但是作为指挥官的绘梨花却因茫茫多的山羊而找不到战舰所在的位置了,于是她将问题交给了身边的你——山羊君,作为一个急于立下战功然后回故乡找山羊子的青年将领,你自然不会放弃这个机会,于是很快就找到了战舰所在的位置,你的这份功绩自然也会被记录到图书之都的文书之中。


输入格式

  第一行一个数test,表示数据组数,以下test部分。
  每部分第一行3个数n,m,k,以下n部分,每部分为mk列的字符矩阵。
  第i部分表示区域(i,0,0)~(i,m-1,k-1)中的战况。
  不同等级的山羊我们用不同的小写英文字母表示,字典序越小的字母表示山羊等级越高。
  相邻部分之间用空行隔开。
  注意下面的样例输入输出中的<空行>表示该行没有任何内容。
 


输出格式

 输出test部分,每部分用空行隔开。
  每部分有t行,t为该组数据中战舰的数目,每行格式为
  ch x y z
  表示编号为ch的战舰的位置为(x,y,z)

  战舰输出顺序无关,如果有多解,输出任意解即可。


样例输入

2
1 2 2
dd
gg
<空行>
3 3 3
aaa
aaa
baa
<空行>
aaa
aaa
baa
<空行>
aaa
aaa
bcc


样例输出

d 0 0 0
g 0 1 0
<空行> 
a 1 1 1
b 1 2 0
c 2 2 1
数据规模和约定
  测试点1~3: n=1,n*m*k<=10
  测试点4~6: n=1,n*m*k<=100
  测试点7~10: n=1,n*m*k<=500
  测试点11~20: n*m*k<=1500
  所有所有数据 test<=10,t<=26
  时间限制:5秒
 

提示

请不要提交!


题目来源

2012国家集训队Round 1 day1

Menuappsclose