P1225 黑白棋游戏

    • 109通过
    • 376提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 搜索 Special Judge 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    黑白棋游戏的棋盘由4×4方格阵列构成。棋盘的每一方格中放有1枚棋子,共有8枚白棋子和8枚黑棋子。这16枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有1条公共边的2个方格称为相邻方格。一个方格最多可有4个相邻方格。在玩黑白棋游戏时,每一步可将任何2个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态,编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。

    输入输出格式

    输入格式:

    输入文件共有8行。前四行是初始游戏状态,后四行是目标游戏状态。每行4个数分别表示该行放置的棋子颜色。“0”表示白棋;“1”表示黑棋。

    输出格式:

    输出文件的第一行是着棋步数n。接下来n行,每行4个数分别表示该步交换棋子的两个相邻方格的位置。例如,abcd表示将棋盘上(a,b)处的棋子与(c,d)处的棋子换位。

    //注:本题可能有多种答案,但是目前洛谷special judge尚未开发完成,因此不保证正确的程序一定ac,结果仅供参考。

    输入输出样例

    输入样例#1: 复制
    1111
    0000
    1110
    0010
    1010
    0101
    1010
    0101
    
    输出样例#1: 复制
    4
    1222
    1424
    3242
    4344
    

    说明

    由@zhouyonglong提供SPJ

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。