hdu2235 机器人的容器

题意:
机器人的容器
Time Limit: 3000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 171 Accepted Submission(s): 33

Problem Description
这是一个n*m的矩形，矩形的每一个单位格子上的高度为h(0<=h<1000)，请问这个容器容量

Input
输入一个正整数T表示有T组数据
对于每组数据第一行输入两个正整数n，m(0<n,m<500)表示矩阵的大小。
接下来有n行，每行m个整数h。

Output
对于每组输入输出一个整数表示容量。

Sample Input

1
4 4
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

Sample Output
4

思路:
这个题目做了一个星期,不过感觉是个好题,感觉这个问题很实际,看到好题就特高兴,
说下思路,一开始用了个很tle的方法,把每一个点都就是一层以层的来,对于没一个点的每一层都是处理新图,0,1看能不能跑出去,如果能ans++,时间复杂度大约是 500 * 500 * 1000 * 500 * 500,sb了,后来我想了下用二分去优化每一个点.二分去找每一个点的最大价值,500 * 500 * lg(1000) * 500 * 500照样跪,说下ac的思路吧(网上的,看了好久想了好久才明白), 先把每一个点都独立出来,按高度从小到大排序,如果高相等,就把是最外边上的点放前面,这样二级排序后我们就得到了一个序列,这个序列的最大特点就是任意两个相邻的点之间都没有"空隙",就是没有高度处于之间的柱子,(我表达不太明白,想一下就知道了),然后我们跑循环,我换个方式写,容易明白

for(i = 1 ;i <= n * m ;i ++)

{
如果当前的这个点没有被标记过(标记过的点从此就没有价值了,被标记就是当前可以流出去)
{

如果当前的这个点是边缘上的点
{
那么直接从改点开始搜,吧所有没标记过并且小于等于当前高度的点全都标记上 ,标记的时候别忘了更新下当前整个图一共已经标记多少个了标记个数很有用..
}
否则
{
如果当前的点的相邻四个点中有被标记过的,那么当前的这个点也就废了,直接从当 前的这个点开始,把小于等于他并且没标记过的全标记上,标记上的都是废的点..
}
如果当前的高小于下一个高
{
(此时就有一个空隙,那么这个空隙的高度是node[i+1].h - node[i].h,空隙的宽度是多少呢 ,其实就是当前开始往前没有作废的点)则 ans += (node[i+1].h - node[i].h) * (i - 作废点的个数,作废点的个数就是全图被标记的个数)
}
}

如果没明白我在说下,所谓的作废点就是可以连接到边缘上的点,因为排序了,高度越来越高,如果当前的这个点是作废点,那么当前这个点和他所连接的作废点一定是以后能连接到当前的点的作废点,排序导致没一个相邻的高度差之间不会有别的高度的东西出现.当前的高度差*当前点个数-作废点个数就是当前这一层的价值...这个题目很赞...天天图论,做做这个也挺好..

#include<stdio.h>
#include<string.h>
#include<algorithm>

#define N_n 505
#define N_N 250050

using namespace std;

typedef struct
{
   int x ,y;
   int high;
   int key;
}NODE;

NODE node[N_N];
int H[N_n][N_n];
int mark[N_n][N_n];
int now_mksum;
int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};
int n ,m;

bool camp(NODE a ,NODE b)
{
   return a.high < b.high || a.high == b.high && a.key > b.key;
}

bool ok(int x ,int y ,int now_h)
{
   if(x >= 1 && x <= n && y >= 1 && y <= m && !mark[x][y] && H[x][y] <= now_h)
   return 1;
   return 0;
}

void MK(int x ,int y ,int now_h)
{
   for(int i = 0 ;i < 4 ;i ++)
   {
      int xx = x + dir[i][0];
      int yy = y + dir[i][1];
      if(ok(xx ,yy ,now_h))
      {
         mark[xx][yy] = 1;
         now_mksum ++;
         MK(xx ,yy ,now_h);
      }
   }
   return;
}

void jude(int x ,int y ,int now_h)
{
   for(int i = 0 ;i < 4 ;i ++)
   {
      int xx = x + dir[i][0];
      int yy = y + dir[i][1];
      if(xx == 0 || xx == n + 1 || yy == 0 || yy == m + 1)
      continue;      
      if(mark[xx][yy])
      {   
         mark[x][y] = 1;
         now_mksum ++; 
         MK(x ,y ,now_h);    
         break;
      }
   }
}

int main ()
{
   int t ,i ,j ,ans;
   scanf("%d" ,&t);
   while(t--)
   {
      scanf("%d %d" ,&n ,&m);
      for(i = 1 ;i <= n ;i ++)
      for(j = 1 ;j <= m ;j ++)
      {
         scanf("%d" ,&H[i][j]);
         int now = (i - 1) * m + j;
         node[now].x = i;
         node[now].y = j;
         node[now].high = H[i][j];
         node[now].key = (i == 1 || i == n || j == 1 || j == m);
      }
      sort(node + 1 ,node + n * m + 1 ,camp);
      memset(mark ,0 ,sizeof(mark));
      for(ans = now_mksum = 0 ,i = 1 ;i <= n * m ;i ++)
      {
         if(node[i].high == node[n*m].high) break;
         if(!mark[node[i].x][node[i].y])
         {
            if(node[i].key) 
            {
               mark[node[i].x][node[i].y] = 1;
               now_mksum ++;
               MK(node[i].x ,node[i].y ,node[i].high);
            }
            else jude(node[i].x ,node[i].y ,node[i].high);
         }
         if(node[i].high < node[i+1].high)
         ans += ((node[i+1].high - node[i].high) * (i - now_mksum));
      }
      printf("%d
" ,ans);
   }
   return 0;
}