TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3828
  • 题目
  • P3828ZZ 的滑动魔方
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1000ms
    问题描述

    聪明伶俐、勤奋好学的ZZ 迷上了一种魔方。
    它是一个3*3 的矩阵,每一块可以为白、蓝、红三种颜色中的一种。每一局游戏会告诉
    你一个初始态和一个还原态,你需要做的是进行一系列操作使得魔方由初始态变为还原态。
    游戏分为简单、普通、困难三种模式,共有左滑、右滑、上滑、下滑、顺时针旋转、逆
    时针旋转六种操作:
    滑动操作:往哪个方向滑,整个矩阵整体向那个方向平移,超出部分填充至新增部分

    ZZ 用自己的聪明才智破解了许多许多关,这使得你跃跃欲试。
    为了变得和ZZ 一样聪明,你要求自己每一局必须要使用最少步数通关。但是因为你是做
    训练赛的时候玩的,所以BOSS_He 要求你只能玩m 局,然后接着做训练赛。
    现在告诉你m 局的起始态和还原态,你要找出每局还原的最小步数。

    输入格式

    包含多组数据,第一行一个整数m,表示局数。
    对于每组数据,第一行一个字母紧接着一个冒号,表示该局游戏的难度,e 表示简单,s 表示
    普通,h 表示困难。
    接着两个3*3 的矩阵,第一个表示起始状态,第二个表示目标状态。
    每个矩阵只包含WBR 三个字母,分别表示白色块、蓝色块、红色块。

    输出格式

    m 行,每行表示对应局的最小解决步数,若无解输出“ZZ”(不含括号)。

    样例输入

    样例1:
    2
    e:
    WWW
    BWR
    WWW
    WBW
    WWW
    WRW
    s:
    WWW
    BWR
    WWW
    WBW
    WWW
    WRW

    样例2:
    2
    h:
    WWW
    BWR
    WWW
    WBW
    WWW
    WRW
    h:
    WWW
    BWR
    WWW
    BWW
    WWW
    WWR

    样例3:
    1
    h:
    BWB
    RBR
    WWW
    WBB
    BWW
    RWR

    样例输出

    样例1:
    1
    2
    样例2:
    1
    1
    样例3:
    7

    提示

    数据范围对于40%的数据,只包含简单模式。
    对于20%的数据,只包含普通模式。
    对于40%的数据,m=1,即只有一局。
    对于100%的数据,1<=m<=800。
    样例说明样例1说明:
    对于第一局,简单模式,只需顺时针旋转90°一次。
    对于第二局,普通模式,需要顺时针旋转45°两次。
    样例2说明:
    对于第一局,困难模式,只需顺时针旋转90°一次。
    对于第二局,困难模式,只需顺时针旋转45°一次。
    样例3(良心样例)说明:


    来源  YXV