梯田（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
搜索题：向四周扩一层然后搜索，要用二分搜索

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 #define Max 1000000

 #define MMax 1000000+100        //表示被淹

 int T,n,m,p,q;

 int map[][];

 int ti[][];

 int H;

 int dirx[]={,,-,,},diry[]={-,,,};

 int dfs(int x,int y,int h)

 {

     int r=;

     if(ti[x][y]==MMax||x<||y<||x>(n+)||y>(m+))

         return ;

     if(ti[x][y]<=h)

     {

         ti[x][y]=MMax;

         for(int i=;i<;i++)

             dfs(x+dirx[i],y+diry[i],h);

     }

     return ;

 }

 int test()

 {

     int sum=;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             if(ti[i][j]==MMax)

                 sum++;

     return sum;

 }

 int main()

 {

     int i,j,k,sum;

     //freopen("in.txt","r",stdin);

     cin>>T;

     while(T--)

     {

         bool flag=;

         cin>>n>>m>>p>>q;

         memset(map,,sizeof(map));

         for(i=;i<=n;i++)

             for(j=;j<=m;j++)

                 cin>>map[i][j];

         int lb=,rb=Max,mid;

         H=Max;

         while(rb-lb>)

         {

             memcpy(ti,map,sizeof(map));

             mid=(lb+rb)/;

             dfs(,,mid);

             sum=test();

             if(sum>q)

                 rb=mid;

             else if(sum<p)

                 lb=mid;

             else

             {

                 rb=mid;

                 flag=;

                 H=mid;

             }

         }

         if(!flag)

             cout<<-<<endl;

         else

             cout<<H<<endl;

     }

 }