P4487 [BJWC2018]Cross sum

    • 2通过
    • 7提交
  • 题目提供者 Xeonacid
  • 评测方式 云端评测
  • 标签 2018 北京 Special Judge 高性能
  • 难度 尚无评定
  • 时空限制 2000ms / 512MB

题解

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

    推荐的相关题目 显示

    题目背景

    首先介绍一下Kakuro(カックロ) 这个游戏。

    游戏规则为:

    • 方形空格中填入1 ~ 9 的整数。

    • 被斜线分开的方格中,右上角的数字等于其右侧邻接之连续方格中数字之和,左下角的数字等于其下方邻接之连续方格中数字之和。

    • 无论是横向还是纵向,连续方格中的数字不能重复。

    左边为一个Kakuro 游戏,右边为这个游戏的唯一解。

    我们称一开始给出的数字为线索,称需要填入数字的地方为空格。如果一个格子包含线索那么就不需要填入数字。我们约定所有的谜题都非空,即至少有一个空格需要被填入。

    注意:在以下题目中的游戏规则可能会有所不同,请认真阅读在每个 题目下的规则。

    题目描述

    游戏规则:

    • 空格中填入正整数。

    • 被斜线分开的方格中,右上角的数字等于其右侧邻接之连续方格中数字之异或和,左下角的数字等于其下方邻接之连续方格中数字之异或和。

    • 所有空格中填入的整数都不能重复。

    Apia 给了Rimbaud 一个Kakuro 谜题。心不灵手不巧的Rimbaud 根本不会做Kakuro,所以她请求你帮她解决。由于Rimbaud 很年幼,只会对不超过$2^{60}-1$ 的数字进行运算。所以希望谜题的解中每个数字都不超过 $2^{60}-1$。

    输入输出格式

    输入格式:

    每组数据包含多组测试数据。第一行包含一个整数T 表示测试数据组数。

    对于每组测试数据,第一行,两个正整数表示n,m 表示这个游戏的行和列。

    接下来n 行,每行包含m 个0 到4 的数字,第i 行第j 列表示第i 行第j 列格子的种类。

    • 0 表示这个格子既不是空格也不是线索。

    • 1 表示这个格子左下角包含线索,右上角没有线索。

    • 2 表示这个格子右上角包含线索,左下角没有线索。

    • 3 表示这个格子左下角右上角都包含线索。

    • 4 表示这个格子为空格。

    输入保证这个从格式上来说一定是个合法的Kakuro 谜题,即每一段连续的空格的左边或者上面的格子包含线索。

    接下来n 行,每行包含若干个非负整数,按从左往右的顺序给出谜题中的每个线索。特别地如果这个格子的种类为3,那么先给出左下角的线索,再给出右上角的线索。

    输出格式:

    对于每组测试数据,如果有解,那么输出n 行,每行按从左往右的顺序输出往空格中填入的数,要求空格内填入的数字在1 到$2^{60}-1$ 之间。否则输出一个-1。

    输入输出样例

    输入样例#1: 复制
    3
    3 3
    0 1 1
    2 4 4
    2 4 4
    3 7
    2
    6
    3 3
    0 1 1
    2 4 4
    2 4 4
    1 1
    1
    1
    2 2
    0 1
    2 4
    0
    0
    输出样例#1: 复制
    1 3
    2 4
    -1
    -1

    说明

    对于10% 的数据,保证$n,m ≤ 3$。

    对于30% 的数据,保证$n,m ≤ 15$。

    对于50% 的数据,保证$n,m ≤ 40$。

    对于另外20% 的数据,保证只有第一行第一列包含线索,剩下的地方全都是空格。

    对于100% 的数据,保证$3 ≤ n,m ≤ 200, T ≤ 5$,保证初始局面中的每个数字不超过$2^{60}-1$。

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