梯田（dfs）

梯田

Time Limit: 2000 ms Memory Limit: 256 MB
Total Submission: 26 Submission Accepted: 5

Description

土豪YZK在一块小岛上有着一大片n*m的梯田，每块1*1的田地都有它的高度。奴隶们不甘被YZK剥削，他们联合起来决定发动一场海啸淹掉YZK的梯田，因为要留一部分给自己吃，所以他们决定至少淹掉p块田地，但是不能超过q块田地，否则会因为剩下的田地不够而把奴隶自己饿死。现在给你一个n*m的矩阵，代表梯田中每块田地的高度，求能否发动一场高度为h的海啸，使得满足奴隶们的要求。由于发动海啸代价很高，所以如果存在多个解，请输出最小的一个h，否则输出-1。
一块田地被淹的条件为：
一、它自身的高度<=h
二、它相邻的四块田地中至少有一块被淹没

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

Input

第一行是一个正整数T，代表数据组数
对于每组数据，第一行为四个整数n，m，p，q
之后是一个n*m的矩阵，矩阵中每个整数代表每块田地高度
1<=T<=100
1<=n,m<=100
1<=p<=q<=n*m
1<=梯田高度<=1000000

Output

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

Sample Input

Sample Output

3
-1
搜索题：向四周扩一层然后搜索，要用二分搜索

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 #define Max 1000000
 7 #define MMax 1000000+100        //表示被淹
 8 int T,n,m,p,q;
 9 int map[105][105];
10 int ti[105][105];
11 int H;
12 int dirx[4]={0,0,-1,1,},diry[4]={-1,1,0,0};
13 int dfs(int x,int y,int h)
14 {
15     int r=0;
16     if(ti[x][y]==MMax||x<0||y<0||x>(n+1)||y>(m+1))
17         return 0;
18     if(ti[x][y]<=h)
19     {
20         ti[x][y]=MMax;
21         for(int i=0;i<4;i++)
22             dfs(x+dirx[i],y+diry[i],h);
23     }
24     return 0;
25 }
26 int test()
27 {
28     int sum=0;
29     for(int i=1;i<=n;i++)
30         for(int j=1;j<=m;j++)
31             if(ti[i][j]==MMax)
32                 sum++;
33     return sum;
34 }
35 int main()
36 {
37     int i,j,k,sum;
38     //freopen("in.txt","r",stdin);
39     cin>>T;
40     while(T--)
41     {
42         bool flag=0;
43         cin>>n>>m>>p>>q;
44         memset(map,0,sizeof(map));
45         for(i=1;i<=n;i++)
46             for(j=1;j<=m;j++)
47                 cin>>map[i][j];
48         int lb=0,rb=Max,mid;
49         H=Max;
50         while(rb-lb>1)
51         {
52             memcpy(ti,map,sizeof(map));
53             mid=(lb+rb)/2;
54             dfs(0,0,mid);
55             sum=test();
56             if(sum>q)
57                 rb=mid;
58             else if(sum<p)
59                 lb=mid;
60             else 
61             {
62                 rb=mid;
63                 flag=1;
64                 H=mid;
65             }
66         }
67         if(!flag)
68             cout<<-1<<endl;
69         else
70             cout<<H<<endl;
71     }
72 }