Your task is to simulate a flood disaster.
For the given cross-section diagram, provide the area of the submerged parts.
Assume that it is continuously raining in the area, and the water overflowing from the area is falling into the sea on both sides. For example, for the above cross-section diagram, the rainwater will create floods with areas of 4, 2, 1, 19, and 9 respectively.
Input
A string is given in one line, using "/", "" and "_" to represent slopes and plains. For example, the area in the above example is given by the string “\ \ / / / \ _ / \ / \ \ \ \ / _ / \ \ / / / _ _ \ \ \ _ \ \ / _ \ / _ / ”.
Output
Output in the following format:
A
K L1,L2,…,Lk
In the first line, print the total area A of the flooded area.
In the second line, print the number of flooded areas K and the area of each area Li (from left to right).
Constraints
1 ≤ length of the string ≤ 20000
Upon seeing this problem, I first thought we could start from the beginning, finding the place where it starts to dip down one step at a time, continuously tracking until the height levels off with the previous one. Then continue until it starts to descend again and repeat the previous process.
Then I realized that it is easy to encounter situations where it can no longer reach the height where it started to descend, so I decisively abandoned this approach and wrote a large simulation:
Directly construct a cross-section diagram, using 0 to represent air, 1 to represent mountains, 2 to represent full water, 3 to represent half water descending, and 4 to represent half water ascending.
First, fill all parts above the mountains with water, then repeatedly execute: throw away water in any direction below that is air until it can no longer be thrown away, and what remains is our accumulated water.
Finally, use DFS to find each clump of water and calculate the area.
Then we found that the map is a two-dimensional array, and defining it as ditu[MAXN][MAXN] would directly exceed space limits. Then we considered that there shouldn't be mountains that continuously descend or ascend, so we tried to open a smaller second dimension.
Two TLEs were encountered.
#include <stdio.h>
#define MAXN 20005
#define INF ((int)0x3f3f3f3f)
#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) < (b) ? (b) : (a))
int a[MAXN] = {0};
int ditu[MAXN][1005] = {0};//0:empty,1:mountain,2:water,3:down_mountain,4:up_mountain
short vis[MAXN][1005] = {0};
int mmjimf[MAXN] = {0};
int newm = 0;
double dfs(int x, int y)
{
if (vis[x][y])
{
return 0.;
}
vis[x][y] = 1;
double value = 0;
switch (ditu[x][y])
{
case 2:
value = 1;
break;
case 3:
case 4:
value = 0.5;
break;
default:
return 0;
}
if (ditu[x][y] == 2) value += dfs(x + 1, y) + dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1);
else if (ditu[x][y] == 3)
{
value += dfs(x + 1, y) + dfs(x, y + 1) + dfs(x, y - 1);
if (ditu[x - 1][y] != 4)
{
value += dfs(x - 1, y);
}
} else if (ditu[x][y] == 4)
{
value += dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1);
if (ditu[x + 1][y] != 3)
{
value += dfs(x + 1, y);
}
}
return value;
}
int main(void)
{
char c = getchar();
int newp = 1;
int zvdi = INF, zvgc = -INF;
while (c == '/' || c == '\\' || c == '_')
{
++newp;
switch (c)
{
case '/':
a[newp] = a[newp - 1] + 1;
break;
case '\\':
a[newp] = a[newp - 1] - 1;
break;
case '_':
a[newp] = a[newp - 1];
break;
}
if (a[newp] < zvdi)
{
zvdi = a[newp];
}
c = getchar();
}
for (int i = 1; i <= newp; ++i)
{
a[i] += (-zvdi + 1);
if (a[i] > zvgc)
{
zvgc = a[i];
}
}
for (int i = 1; i < newp; ++i)
{
int low = min(a[i], a[i + 1]);
int high = max(a[i], a[i + 1]);
for (int j = 1; j <= zvgc; ++j)
{
if (j <= low)
{
ditu[i][j] = 1;
} else if (j >= low && j <= high)
{
if (low != high)
{
if (a[i] > a[i + 1]) ditu[i][j] = 3;
else ditu[i][j] = 4;
} else
{
ditu[i][j] = 2;
}
} else if (j > high)
{
ditu[i][j] = 2;
}
}
}
int vcdc = 0;
do
{
vcdc = 0;
for (int j = zvgc; j >= 1; --j)
{
for (int i = 1; i < newp; ++i)
{
if (ditu[i][j] == 2 || ditu[i][j] == 3 || ditu[i][j] == 4)
{
if (!((ditu[i - 1][j] || ditu[i][j] == 3) && (ditu[i + 1][j] || ditu[i][j] == 4) && ditu[i][j - 1]))
{
++vcdc;
ditu[i][j] = 0;
}
}
}
}
} while (vcdc);
double mmji = 0;
for (int j = zvgc; j >= 1; --j)
{
for (int i = 1; i < newp; ++i)
{
switch (ditu[i][j])
{
case 2:
mmji += 1;
break;
case 3:
case 4:
mmji += 0.5;
break;
}
}
}
printf("%.0lf\n", mmji);
for (int i = 1; i < newp; ++i)
{
for (int j = zvgc; j >= 1; --j)
{
if (!vis[i][j])
{
double ans = dfs(i, j);
if (ans) mmjimf[++newm] = ans;
}
}
}
printf("%d ", newm);
for (int i = 1; i <= newm; ++i)
{
printf("%d ", mmjimf[i]);
}
return 0;
}
Encountering serious TLE, I felt very sad and opened Bing, searching the entire internet, and found a solution. This solution told us
From the submerged area, we can think of the pairing of '' and '/'.
This problem is particularly special in how to form a whole submerged interval? The answer is to merge all paired intervals that are mutually contained.
How to merge? It can be known that the smaller intervals contained in the larger interval must be pushed onto the stack first, so we can merge them accordingly.
How to calculate the cross-sectional area? All paired '' and '/' between form trapezoids or triangles, breaking the problem down into smaller problems to solve.
After reading this, I was greatly inspired and decided to write according to this idea. After writing a bit, I found that there was no need for a stack; it seemed that simple addition and subtraction would suffice.
At this point, I realized that as long as I made the initial approach a bit more brute force, starting from each starting point, if I could no longer reach the height where I started to descend, I would discard this starting point and move to the next one. This approach not only wouldn't waste too much space but also would be much faster than the large simulation, resulting in a successful AC.
#include <stdio.h>
#define MAXN 20005
char sgn[MAXN] = {0};
double ans[MAXN] = {0};
double tot = 0;
int news = 0;
int newa = 0;
int main()
{
int h = 0;
char t = getchar();
while (t == '/' || t == '\\' || t == '_')
{
sgn[++news] = t;
t = getchar();
}
int i = 1;
while (i <= news)
{
double sum = .5, hi = 1;
if (sgn[i] != '\\')
{
++i;
continue;
}
int st = 1;
int j;
for (j = i + 1; j <= news && st > 0; ++j)
{
if (sgn[j] == '\\')
{
++st;
++hi;
sum += (hi - .5);
} else if (sgn[j] == '/')
{
--st;
--hi;
sum += (hi + .5);
} else
{
sum += hi;
}
}
if (st == 0)
{
i = j;
ans[++newa] = sum;
tot += sum;
} else
{
++i;
}
}
printf("%.0lf\n%d ", tot, newa);
for (int i = 1; i <= newa; ++i)
{
printf("%.0lf ", ans[i]);
}
return 0;
}
The rehabilitation journey is ongoing~~