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 on 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 region 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 a situation where we can no longer reach the height we started descending from, 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 whole units of water, 3 to represent half units of descending water, and 4 to represent half units of ascending water.
First, fill all parts above the mountains with water, then repeatedly execute: throw away any water that has air below it on either side 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.
Received two TLEs
#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:downhill,4:uphill
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 timeout TLE, I felt very sad and opened Bing, searching the entire internet, and found a solution. This solution tells us
From the submerged area, we can think of pairing '' 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 them 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 segment, 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 I started descending from, I would discard this starting point and move on to the next one. This approach would not waste too much space and would be much faster than the large simulation, successfully achieving 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~~