P4578 [FJOI2018]所罗门王的宝藏

    • 145通过
    • 364提交
  • 题目提供者 和泉正宗
  • 评测方式 云端评测
  • 标签 图论 枚举,暴力 各省省选 2018 福建 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    据古代传说记载,所罗门王既是智慧的代表,又是财富的象征。他建立了强大而富有的国家,聚集了大批的黄金象牙和钻石,并把这些价值连城的珍宝藏在一个神秘的地方,这就是世人瞩目的“所罗门王的宝藏”。多少个世纪以来,人们一直在寻找这批早已失落的古代文明宝藏,寻找盛产黄金和钻石的宝地。曾经追寻所罗门王宝藏的冒险者们都一去不回,至今没人解开这个谜题。亨利男爵在一次幸运的旅途中意外地得到了三百年前一位葡萄牙贵族留下的写在羊皮卷上的所罗门王的藏宝图和一本寻宝秘籍。在这张藏宝图的诱惑下,亨利男爵邀请约翰上校和勇敢的猎象人夸特曼开始了寻找埋葬在黑暗地底的所罗门王宝藏的艰险历程。他们横穿渺无边际的沙漠和浓荫蔽日的原始森林,越过汹涌澎湃的激流险滩,翻越高耸入云的峻岭雪山,饱尝沙漠的酷热和冰雪严寒,在藏宝图的指引下来到非洲一个原始的神秘国度库库安纳。这里有残酷的人殉制度,有一个拥有一千个妻室的独眼暴君特瓦拉,有像兀鹫一般丑恶诡诈老而不死的女巫加古尔,还有美丽聪慧的绝代佳人弗拉塔。在这片陌生而又险象环生的土地上三位寻宝英雄历尽艰辛,终于在绝代佳人弗拉塔的帮助下在海底深处找到了珍藏这批价值连城宝藏的巨大的藏宝洞。然而在女巫加古尔的精心策划下,一场灭顶之灾正在悄悄逼近。

    藏宝洞的洞门十分坚固且洞门紧闭,如果不知道开启洞门的秘密是无法打开藏宝洞的洞门。在藏宝洞的洞门一侧有一个奇怪的矩形密码阵列。根据寻宝秘籍的记载,在密码阵列每行的左侧和每列的顶端都有一颗红宝石按钮。每个按钮都可以向左或向右转动。每向左转动一次按钮,相应的行或列中数字都增 $1$。每向右转动一次按钮,相应的行或列中数字都减 $1$。在矩形密码阵列的若干特定位置镶嵌着绿宝石。只有当所有绿宝石位置的数字与藏宝图记载的密码完全相同,紧闭的洞门就会自动缓缓打开。女巫加古尔早已得知开门的秘密。为了阻止寻宝者打开洞门,女巫加古尔为开门的密码阵列设置了全 $0$ 的初始状态。试图打开洞门的寻宝者如果不能迅速转动按钮使所有绿宝石位置的数字与藏宝图记载的密码完全相同,就会自动启动藏宝洞玄妙的暗器机关,使寻宝者遭到灭顶攻击而死于非命。

    您能帮助三位寻宝英雄顺利打开藏宝洞的洞门吗?

    编程任务:对于给定的密码阵列,找到获得正确密码的红宝石按钮的转动序列。

    输入输出格式

    输入格式:

    输入的第一行中有一个正整数 $T (T \le 5)$ 表示有 $T$ 组数据。每组数据的第一行有 $3$ 个正整数 $n,m$ 和 $k$,表示洞门密码阵列共有 $n$ 行和 $m$ 列,$0<n,m,k \le 1000$。各行从上到下依次编号为 $1,2,\ldots,n$;各列从左到右依次编号为 $1,2,\ldots,m$ 。接下来的 $k$ 行中每行有三个整数 $x,y,c$,分别表示第 $k$ 个绿宝石在密码阵列中的位置和密码,$x$ 为行号 $y$ 为列号,$c$ 为该位置处的密码。

    输出格式:

    对于每组数据,用一行输出 Yes 或者 No。输出 Yes 表示存在获得正确密码的红宝石按钮的转动序列。输出 No 则表示无法找到获得正确密码的红宝石按钮的转动序列。

    输入输出样例

    输入样例#1: 复制
    2
    2 2 4
    1 1 0
    1 2 0
    2 1 2
    2 2 2
    2 2 4
    1 1 0
    1 2 0
    2 1 2
    2 2 1
    输出样例#1: 复制
    Yes
    No

    说明

    对于 $100\%$ 的数据,$1 \le n, m, k \le 1000$,$k \le n \times m$,$|c| \le 1,000,000$。

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