Description
AKD市處在一個四面環(huán)山的谷地里。最近一場大暴雨引發(fā)了洪水，AKD市全被水淹沒了。Blue Mary，AKD市的市 長，召集了他的所有顧問（包括你）參加一個緊急會議。經(jīng)過細(xì)致的商議之后，會議決定，調(diào)集若干巨型抽水機(jī)， 將它們放在某些被水淹的區(qū)域，而后抽干洪水。你手頭有一張AKD市的地圖。這張地圖是邊長為m*n的矩形，被劃分 為m*n個1*1的小正方形。對于每個小正方形，地圖上已經(jīng)標(biāo)注了它的海拔高度以及它是否是AKD市的一個組成部分 。地圖上的所有部分都被水淹沒了。并且，由于這張地圖描繪的地面周圍都被高山所環(huán)繞，洪水不可能自動向外排 出。顯然，我們沒有必要抽干那些非AKD市的區(qū)域。每個巨型抽水機(jī)可以被放在任何一個1*1正方形上。這些巨型抽 水機(jī)將持續(xù)地抽水直到這個正方形區(qū)域里的水被徹底抽干為止。當(dāng)然，由連通器原理，所有能向這個格子溢水的格 子要么被抽干，要么水位被降低。每個格子能夠向相鄰的格子溢水，“相鄰的”是指（在同一高度水平面上的射影 ）有公共邊。 Input
第一行是兩個數(shù)m,n(1<=m，n<=1000). 以下m行，每行n個數(shù)，其絕對值表示相應(yīng)格子的海拔高度；若該數(shù)為正 ，表示他是AKD市的一個區(qū)域；否則就不是。請大家注意:所有格子的海拔高度其絕對值不超過1000,且可以為零. Output
只有一行，包含一個整數(shù)，表示至少需要放置的巨型抽水機(jī)數(shù)目。 Sample Input 6 9
-2 -2 -1 -1 -2 -2 -2 -12 -3
-2 1 -1 2 -8 -12 2 -12 -12
-5 3 1 1 -12 4 -6 2 -2
-5 -2 -2 2 -12 -3 4 -3 -1
-5 -6 -2 2 -12 5 6 2 -1
-4 -8 -8 -10 -12 -8 -6 -6 -4
Sample Output 2
解題方法：參考PO爺?shù)牟┛停琌TZ PO爺
我們首先考慮如果在格子 a 修建一個抽水機(jī)，在什么情況下格子 b 的水也可以被抽干。我們可以發(fā)現(xiàn)當(dāng)且僅當(dāng)存在一條從 a 到 b 的路徑，中間經(jīng)過的抽水機(jī)（包括 a）的高度都不大于 b 的高度。因此我們可以考慮把所有格子的高度從小到大排序，我們把每一個格子建成一個集合。然后按照海拔高度從小到大掃描格子，對于當(dāng)前的格子 i，我們找到所有與 i 相鄰并且海拔高度不大于格子 i 的格子，我們發(fā)現(xiàn)如果這些格子中的任意一個洪水要是被解決了，那么格子 i 的洪水也可以被解決，所以我們合并這些格子。對于當(dāng)前的格子 i，如果它必須被清理且與它相鄰的格子集合中沒有任何一個被清理，我們則把這個集合的清理狀態(tài)標(biāo)記為真，然后答案加 1。集合和每個格子是否被清理用并查集來維護(hù)就可以了。
代碼如下:
#include <bits/stdc++.h>using namespace std;const int maxn = 1010;int n, m, tot, ans, a[maxn][maxn];int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};struct node{ int x, y, height; node(){} node(int x, int y, int height) : x(x), y(y), height(height) {} bool Operator <(const node &rhs) const{ return height < rhs.height; }}city[maxn*maxn], maze[maxn*maxn];bool flag[maxn][maxn];pair <int, int> fa[maxn][maxn];pair <int, int> find_set(pair <int, int> x){ if(x == fa[x.first][x.second] || fa[x.first][x.second] == make_pair(0, 0)) return fa[x.first][x.second] = x; else return fa[x.first][x.second] = find_set(fa[x.first][x.second]);}void union_set(pair <int, int> x, pair <int, int> y){ x = find_set(x), y = find_set(y); if(x != y){ fa[x.first][x.second] = y; flag[y.first][y.second] |= flag[x.first][x.second]; }}void cha(int x, int y){ for(int i = 0; i < 4; i++){ int tx = x + dir[i][0], ty = y + dir[i][1]; if(tx <= 0 || ty <= 0 || tx > m || ty > n) continue; if(a[tx][ty] > a[x][y]) continue; union_set(make_pair(x, y), make_pair(tx, ty)); }}int main(){ scanf("%d%d", &m, &n); for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ scanf("%d", &a[i][j]); if(a[i][j] > 0) city[++tot] = node(i, j, a[i][j]); else{ a[i][j] = -a[i][j]; } maze[i*n - n + j] = node(i, j, a[i][j]); } } sort(city + 1, city + 1 + tot); sort(maze + 1, maze + 1 + n * m); for(int i = 1, j = 1; i <= tot; i++){ for(; j <= m*n && maze[j].height <= city[i].height; j++) cha(maze[j].x, maze[j].y); pair <int, int> now = find_set(make_pair(city[i].x, city[i].y)); if(flag[now.first][now.second]) continue; ++ans, flag[now.first][now.second] = 1; }新聞熱點(diǎn)
疑難解答
