最近和同学在准备一个元旦晚会的节目，wonder girls 的一段mv舞蹈：tell me。 胡思乱想中想到一个很有意思的小问题，设计的好的话其实可以作为比赛中前菜。。用来热身。。不算很水。。但是也不难。。有几个小tricks还是要稍微注意下，下面简单的描述一下。
现在有五位同学在练习舞蹈，五位同学有一定的队形，在舞蹈中需要时常变换队形，那么请问从当前队形变换成指定队形至少需要做多少次队形转换。我们规定五位同学一次队形转换定义如下:
1.五位同学中必须至少有一位同学移动，且只能移动一步。
2.移动的位置必须为空或者即将为空，即将为空的意思是两个同步移动。
3.移动的方向是周围的8个方向。
比如如下图所示：（左边为当前位置，右边是目标位置）
可以知道只需要一次转化即可转为目标位置，如下图：
下面作出其他题目假设，题目输入每次都给出两个五行五列的矩阵，0表示该位置有人，1表示该位置没有人，要求移动时不能超出这个5*5的矩阵（这个约束是为了简化计算，如果不限定这个约束题目好像会更开放一些，还没想清楚如果不约束怎么搞）,
比如上图可以给出如下输入：
0 0 0 0 0 1 1 1 0 0
0 1 0 0 0 1 1 0 0 0
1 1 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
输出答案：1
ps： 要注意要求的图形是形状相同即可。。并不要求在矩阵中的相对位置也必须相同。
posted on 2009-11-02 21:39
zoyi 阅读(345)
评论(0) 编辑 收藏 引用 所属分类:
acm