1687：積水問題時間限制: 1000 ms 記憶體限制: 262144 KB
【題目描述】
有一塊矩形土地被劃分成n×m個正方形小塊，這些小塊高低不平，每一小塊都有自己的高度，水流可以由任意一塊地流向周圍四個方向的四塊地中，但是不能直接流入對角相連的小塊中，
一場大雨后，由于地勢高低不同，許多地方都積存了不少降水（這些雨水會不斷下，直到積水不再上升），
給定每個小塊的高度，求每個小塊的積水高度，
注意：假設矩形地外圍無限大且高度為0，即從內部流出來的雨水會在外圍消失，
【輸入】
第一行包含兩個非負整數n,m，
接下來n行每行m個整數表示第i行第j列的小塊的高度，
【輸出】
輸出n行，每行m個由空格隔開的非負整數，表示每個小塊的積水高度，
【輸入樣例】
3 3
4 4 0
2 1 3
3 3 -1
【輸出樣例】
0 0 0
0 1 0
0 0 1
【提示】【資料規模與約定】
對于20%的資料，n,m≤4，
對于40%的資料，n,m≤15，
對于60%的資料，n,m≤50，
對于100%的資料，n,m≤300，|小塊高度|≤109，
在每一部分資料中，均有一半資料保證小塊高度非負，
代碼
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 386;
int G[N][N];
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int f[N * N];
int n, m;
int get(int u)
{
if (f[u] == u)
return u;
else
return f[u] = get(f[u]);
}
void merge(int a, int b)
{
int fa = get(a);
int fb = get(b);
if (fa != fb)
f[fa] = fb;
}
struct node
{
int x, y;
inline bool operator<(const node &a) const
{
return G[x][y] < G[a.x][a.y];
}
} map_list[N * N];
int pos[N][N];
bool vis[N][N];
bool tag[N * N]; //流到邊界
void bfs(int sx, int sy)
{
queue<node> Q;
Q.push(node({sx, sy}));
vis[sx][sy] = true;
int sp = pos[sx][sy];
vector<node> L;
while (!Q.empty())
{
L.push_back(Q.front());
int ux = Q.front().x;
int uy = Q.front().y;
Q.pop();
for (int i = 0; i < 4; i++)
{
int vx = ux + dx[i];
int vy = uy + dy[i];
if (vx > 0 && vx <= n && vy > 0 && vy <= m)
{
if (G[vx][vy] < G[ux][uy] && tag[get(pos[vx][vy])])
tag[get(sp)] = true;
if (vis[vx][vy] || G[vx][vy] != G[ux][uy])
continue;
Q.push(node({vx, vy}));
vis[vx][vy] = true;
merge(pos[vx][vy], sp);
}
}
}
for (auto i : L)
{
int ux = i.x;
int uy = i.y;
for (int j = 0; j < 4; j++)
{
int vx = ux + dx[j];
int vy = uy + dy[j];
if (vx > 0 && vx <= n && vy > 0 && vy <= m && vis[vx][vy])
{
if (G[ux][uy] > G[vx][vy] && !tag[get(pos[vx][vy])])
merge(pos[vx][vy], sp);
}
}
}
}
int idx[N * N][2];
int main()
{
cin >> n >> m;
n += 2;
m += 2;
int tot = 0;
for (int i = 2; i < n; i++)
for (int j = 2; j < m; j++)
{
cin >> G[i][j];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
map_list[++tot] = {i, j};
f[tot] = tot;
idx[tot][0] = i;
idx[tot][1] = j;
pos[i][j] = tot;
if (i == 1 || i == n || j == 1 || j == m)
tag[tot] = true;
}
sort(map_list + 1, map_list + tot + 1);
for (int i = 1; i <= tot; i++)
{
if (!vis[map_list[i].x][map_list[i].y])
bfs(map_list[i].x, map_list[i].y);
}
for (int i = 2; i < n; i++)
{
for (int j = 2; j < m; j++)
{
int p = get(pos[i][j]);
cout << G[idx[p][0]][idx[p][1]] - G[i][j] << ' ';
}
cout << endl;
}
return 0;
}
|
