Problem 1499 --梯田

1499: 梯田

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $52$ 正确数量 $44$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 模拟
土豪YZK在一块小岛上有着一大片n*m的梯田,每块1*1的田地都有它的高度。奴隶们不甘被YZK剥削,他们联合起来决定发动一场海啸淹掉YZK的梯田,因为要留一部分给自己吃,所以他们决定至少淹掉p块田地,但是不能超过q块田地,否则会因为剩下的田地不够而把奴隶自己饿死。现在给你一个n*m的矩阵,代表梯田中每块田地的高度,求能否发动一场高度为h的海啸,使得满足奴隶们的要求。由于发动海啸代价很高,所以如果存在多个解,请输出最小的一个h,否则输出-1。
第一行是一个正整数T,代表数据组数

对于每组数据,第一行为四个整数n,m,p,q

之后是一个n*m的矩阵,矩阵中每个整数代表每块田地高度

1<=T<=100

1<=n,m<=100

1<=p<=q<=n*m

1<=梯田高度<=1000000

对于每组数据,如果能找到h,请输出最小的h,否则输出-1

每组输出占一行

2
3 3 3 6
1 2 3
4 5 6
7 8 9
4 4 5 6
1 2 2 1
2 1 1 2
2 1 1 2
1 2 2 1
3
-1
一块田地被淹的条件为:
一、它自身的高度<=h
二、它相邻的四块田地中至少有一块被淹没

我们可以认为,海啸发动的时候,梯田的外面都处于被淹没状态。

推荐代码 查看1499 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] yaoking 613287 2020-09-27 20:19:32
内存最少[$944 $KB] 未实名用户 86192 2017-05-06 10:31:40
第一AC 未实名用户 86192 2017-05-06 10:31:40
第一挑战 未实名用户 86192 2017-05-06 10:31:40

赛题来源/所属竞赛 2015 Anhui College Student Programming Contest N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛