I 梯田
Time Limit: 3000/1000MS (C++)
问题描述
土豪YZK在一块小岛上有着一大片n*m的梯田，每块1*1的梯田都有它的高度。奴隶们不甘被YZK剥削，他们联合起来决定发动一场海啸淹掉YZK的梯田，因为要留一部分给自己吃，所以他们决定至少淹掉p块田地，但是不能超过q块田地，否则会因为剩下的田地不够而把奴隶自己饿死。现在给你一个n*m的矩阵，矩阵中的元素代表梯田中每块田地的高度，求能否发动一场高度为h的海啸，满足奴隶们的要求。由于发动海啸代价很高，所以如果存在多个解，请输出最小的一个h，否则输出-1。当梯田高度及其周围8方向梯田高度均小于等于海啸高度h时，认为梯田被淹。
输入
第一行是一个正整数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