https://ac.nowcoder.com/acm/contest/403/A

解析：該題很明顯是一道搜索題。首先我們必須明確在什么情況下會形成水洼：即當某一點的高度小于等于( <= )上下左右四個方向時，會形成水洼。

? ? ? ? ?? 該題是要計算形成水洼的面積，那么我們的某一塊最大存水量一定是四個方向上最小的高度。

?

第一次的寫法：只是使用深搜去枚舉每一個點，但寫完發(fā)現這樣寫是有問題，對每一點枚舉時，只是一直在對周圍比較，卻沒有考慮離該點更遠的點，這樣顯然時不對的

wa的代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string>using namespace std;const int maxn = 1e3+5; const int INF = 1e9+7;int a[maxn][maxn]; int h[maxn][maxn]; int vis[maxn][maxn]; int n, m;int xx[] = {0, -1, 0, 1}; int yy[] = {-1, 0, 1, 0};void dfs(int x, int y){//printf("%d %d\n", x, y);if(x == n && y == m){// printf("%d %d\n", x, y);return ;}if(y <= m) dfs(x, y+1);int num = 0, mi = INF;if(!vis[x][y]){for(int i = 0; i < 4; i++){int dx, dy; dx = x + xx[i];dy = y + yy[i];if(dx >= 1 && dx <= n && dy >= 1 && dy <= m){if(a[x][y] <= h[dx][dy]){num++;mi = min(mi, h[dx][dy]);}}}//printf("!!!!! %d %d\n", mi, num);}if(num == 4){h[x][y] = mi;}vis[x][y] = 1;if(x <= n) dfs(x+1, y); }int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){scanf("%d", &a[i][j]);h[i][j] = a[i][j];if(i == 1 || i == n || j == 1 || j == m)vis[i][j] = 1;} int ans = 0;dfs(1, 1);for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){printf("%d ", h[i][j]);}printf("\n");}printf("%d\n", ans);return 0; }/* 0 0 0 0 0 0 0 0 0 0 0 5 2 6 4 3 1 7 8 0 0 6 4 2 3 5 1 4 6 0 0 3 6 4 1 2 4 7 8 0 0 2 5 5 1 2 3 4 4 0 0 2 3 1 5 4 4 1 4 0 0 4 1 2 3 4 5 2 1 0 0 7 5 5 1 5 4 5 7 0 0 1 3 5 5 4 6 8 7 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 5 2 6 4 3 1 7 8 0 0 6 4 3 3 5 1 4 6 0 0 3 6 4 1 2 4 7 8 0 0 2 5 5 1 2 3 4 4 0 0 2 3 2 5 4 4 2 4 0 0 4 2 2 3 4 5 2 1 0 0 7 5 5 3 5 5 5 7 0 0 1 3 5 5 4 6 8 7 0 0 0 0 0 0 0 0 0 0 0 */

使用已經確定的點來不斷更新未確定的點，知道遍歷所有的點。在這里使用堆來進行維護，可以更加方便。ac

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<queue>using namespace std;const int maxn = 1e3+5;struct Node{int x, y, h;bool operator < (const Node &a) const {return h > a.h;} };priority_queue<Node>pq; int a[maxn][maxn]; int h[maxn][maxn]; int vis[maxn][maxn];int n, m;int xx[] = {0, -1, 0, 1}; int yy[] = {-1, 0, 1, 0};int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){scanf("%d", &a[i][j]);h[i][j] = a[i][j];if(i == 1 || i == n || j ==1 || j == m){vis[i][j] = 1;pq.push(Node{i, j, a[i][j]});}}}while(!pq.empty()){Node t = pq.top(); pq.pop();int tmph = t.h;for(int i = 0; i < 4; i++){int dx = t.x + xx[i];int dy = t.y + yy[i];if(dx < 1 || dx > n || dy < 1 || dy > m || vis[dx][dy]) continue;h[dx][dy] = max(h[dx][dy], tmph);vis[dx][dy] = 1;pq.push(Node{dx, dy, h[dx][dy]});}}long long ans = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){//ans += (h[i][j] - a[i][j]) * 1LL;printf("%d ", h[i][j]);}printf("\n"); }printf("%lld\n", ans);return 0; } /* 0 0 0 0 0 0 0 0 0 0 0 5 2 6 4 3 1 7 8 0 0 6 4 2 3 5 1 4 6 0 0 3 6 4 1 2 4 7 8 0 0 2 5 5 1 2 3 4 4 0 0 2 3 1 5 4 4 1 4 0 0 4 1 2 3 4 5 2 1 0 0 7 5 5 1 5 4 5 7 0 0 1 3 5 5 4 6 8 7 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 5 2 6 4 3 1 7 8 0 0 6 4 4 4 5 1 4 6 0 0 3 6 4 4 4 4 7 8 0 0 2 5 5 4 4 4 4 4 0 0 2 3 3 5 4 4 2 4 0 0 4 3 3 3 4 5 2 1 0 0 7 5 5 3 5 5 5 7 0 0 1 3 5 5 4 6 8 7 0 0 0 0 0 0 0 0 0 0 0 */

?

總結

以上是生活随笔為你收集整理的用水填坑 （牛客）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。