hdu3329 二分+搜索

题意：

给你一个岛，然后岛的外侧开始涨水（内侧不涨只有外侧，也就是里面的0永远是0），问最少涨水多少才能把岛分成两个或者两个以上。

思路：

可以二分枚举水的高度（数据不大估计暴力也能过），然后搜索，先把水能覆盖的全都标记上，然后在搜索，看看标记完水之后还有几个岛屿。

#include<stdio.h>

#include<string.h>

#define N 111

#define INF 1000000000



int map[N][N];

int mark[N][N];

int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};

int n ,m;

int ok (int x ,int y)

{

   return x <= n && x >= 1 && y <= m && y >= 1 && !mark[x][y];

}

void DFS(int x ,int y ,int now)

{

   mark[x][y] = 1;

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

   {

      int xx = x + dir[i][0];

      int yy = y + dir[i][1];

      if(ok(xx ,yy) && now >= map[xx][yy]) DFS(xx ,yy ,now);

   }

}

int get_sum(int now)

{

   int i ,j ,sum;

   memset(mark ,0 ,sizeof(mark));

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

   {

      if(now >= map[i][1] && !mark[i][1]) DFS(i ,1 ,now);

      if(now >= map[i][m] && !mark[i][m]) DFS(i ,m ,now);

   }

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

   {

      if(now >= map[1][i] && !mark[1][i]) DFS(1 ,i ,now);

      if(now >= map[n][i] && !mark[n][i]) DFS(n ,i ,now);

   } 

   for(sum = 0 ,i = 1 ;i <= n ;i ++)

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

   if(!mark[i][j])

   {

      sum ++;

      DFS(i ,j ,INF);

   }

   return sum;

}

int main ()

{

   int i ,j ,ans ,cas = 1;

   int low ,up ,mid;

   while(~scanf("%d %d" ,&n ,&m) && n + m)

   {

      for(up = -1 ,i = 1 ;i <= n ;i ++)

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

      {

         scanf("%d" ,&map[i][j]);

         if(i == 1 || i == n || j == 1 || j == m)

         up = up < map[i][j] ? map[i][j] : up;

      }

      low = 0 ,ans = -1;

      while(low <= up)

      {

         mid = (low + up) >> 1;

         int now = get_sum(mid);

         if(now >= 2)

         {

            ans = mid;

            up = mid - 1;

         }

         else low = mid + 1;

      }

      printf("Case %d: " ,cas ++);

      ans == -1 ? puts("Island never splits.") : printf("Island splits when ocean rises %d feet.\n" ,ans);

   }

   return 0;

}

巴特西

hdu3329 二分+搜索

最新文章

热门文章