題意：
? ? ? 給你一個(gè)島，然后島的外側(cè)開始漲水（內(nèi)側(cè)不漲只有外側(cè)，也就是里面的0永遠(yuǎn)是0），問最少漲水多少才能把島分成兩個(gè)或者兩個(gè)以上。


思路：
? ? ? 可以二分枚舉水的高度（數(shù)據(jù)不大估計(jì)暴力也能過），然后搜索，先把水能覆蓋的全都標(biāo)記上，然后在搜索，看看標(biāo)記完水之后還有幾個(gè)島嶼。

?

#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; }

總結(jié)

以上是生活随笔為你收集整理的hdu3329 二分+搜索的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。