Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5358 --宫室宝藏
5358: 宫室宝藏
警告!
题目
状态
题解
题目描述
有一座地下宫殿呈矩阵状,由 $R\times C$ 间矩形宫室组成,其中有 $N$ 间宫室里埋藏着宝藏,称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔,由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这 $N$ 间藏宝宫室每间都架设了一扇传送门,没有宝藏的宫室不设传送门,所有的宫室传送门分为三种: “横天门”:由该门可以传送到同行的任一宫室; “纵寰门”:由该门可以传送到同列的任一宫室; “任意门”:由该门可以传送到以该门所在宫室为中心周围8格中任一宫室(如果目标宫室存在的话)。 深谋远虑的小明当然事先就搞到了所驼门王当年的宫殿招标册,书册上详细记录了每扇传送门所属宫室及类型。而且,虽然宫殿内外相隔,但他自行准备了一种便携式传送门,可将自己传送到殿内任意一间宫室开始寻宝,并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次,且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制,每间宫室也可以多次出入。 现在小明已经打开了便携门,即将选择一间宫室进入。为得到尽多宝藏,他希望安排一条路线,使走过的不同藏宝宫室尽可能多。请你告诉小明这条路线最多行经不同藏宝宫室的数目。
输入
第一行给出三个正整数 $N,R,C$。 以下 $N$ 行,每行给出一扇传送门的信息,包含三个正整数 $x_i,y_i,T_i$,表示该传送门设在位于第 $x_i$ 行第 $y_i$ 列的藏宝宫室,类型为 $T_i$。$T_i$ 是一个 $1\sim 3$ 间的整数,$1$ 表示可以传送到第 $x_i$ 行任意一列的“横天门”,$2$ 表示可以传送到任意一行第 $y_i$ 列的“纵寰门”,$3$ 表示可以传送到周围 $8$ 格宫室的“任意门”。
输出
一个正整数,表示你确定的路线所经过不同藏宝宫室的最大数目。
样例输入输出
输入#1
复制
10 7 7 2 2 1 2 4 2 1 7 2 2 7 3 4 2 2 4 4 1 6 7 3 7 7 1 7 5 2 5 2 1
输出#1
复制
9
提示
对于 $100\%$ 的数据,保证 $1 \leq N \leq 10^5$,$1 \leq x_i \leq R \leq 10^6$,$1\leq y_i \leq C \leq 10^6$,所有的传送门位置互不相同。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
未评定
标签
点击显示
if ($pr_flag) { ?>
递交数
2
已通过
2
} ;?>
通过率
100%
时间限制
1 秒
内存限制
256 MB
来源
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和