专栏文章
题解:P5053 [COCI 2017/2018 #7] Clickbait
P5053题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mip15k9v
- 此快照首次捕获于
- 2025/12/03 04:28 3 个月前
- 此快照最后确认于
- 2025/12/03 04:28 3 个月前
题目大意
现在有很多容器竖着挂在墙壁上,有许多管道连接它们。最开始往容器里注水,求容器注满的顺序。
解法
手模样例,我们发现水位从下到上,每遇到一根管道就会往管道连接的容器注水,直到注满为止。
于是就可以采用 DFS 算法进行模拟。
对于每个容器,遍历水位从下到上,判断两边是否有管道连接,如果有就沿着管道走,走到新容器后重复本步骤。
题目比较人性化的一点在于同一水位不会有两根管道连接,这样就不需要用作者极度匮乏的科学知识考虑特殊情况了。
代码
CPP#include <bits/stdc++.h>
#define int long long
const int N = 1005;
const int Mod = 1e9 + 7;
using namespace std;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m;
char a[N][N];
inline pair<int, int> getHW(int x, int y) // 获取高和长
{
int h = 1, w = 1; // h:高 w:长
while (a[x + h][y] != '+')
{
h++;
}
while (a[x][y + w] != '+')
{
w++;
}
w++, h++;
return {h, w};
}
inline int getId(int x, int y, int h, int w) // 获取当前容器编号
{
for (int i = x; i <= x + h - 1; i++)
{
for (int j = y; j <= y + w - 1; j++)
{
if (a[i][j] >= '0' && a[i][j] <= '9')
{
string str;
while (a[i][j] >= '0' && a[i][j] <= '9')
{
str += a[i][j];
j++;
}
return stoi(str);
}
}
}
return -1;
}
void dfs(int u, int x, int y) // 箱子编号为 u,(x, y) 是容器边框上第一行的点
{
while (a[x][y] != '+') // 将 (x, y) 移至容器左上角
{
y--;
}
auto [h, w] = getHW(x, y);
u = getId(x, y, h, w);
for (int i = x + h - 2; i >= x - 1; i--) // 从下往上加水
{
if (a[i][y - 1] == '-' || a[i][y + w] == '-') // 左右有管道连接
{
int nx = i, ny, dir;
if (a[i][y - 1] == '-') // 左
{
ny = y - 1, dir = 3;
}
else // 右
{
ny = y + w, dir = 1;
}
while (true)
{
nx += dx[dir], ny += dy[dir];
if (a[nx][ny] == '+') // 来到转折处
{
if (dir % 2) // 横着,只能往下
{
dir = 2;
}
else // 竖着,左右都有可能
{
if (a[nx][ny - 1] == '-') // 左
{
dir = 3;
}
else if (a[nx][ny + 1] == '-') // 右
{
dir = 1;
}
}
}
else if (a[nx - dx[dir]][ny - dy[dir]] == '|' && a[nx][ny] == '-') // 碰到容器
{
break;
}
}
dfs(0, nx, ny);
}
}
cout << u << endl;
}
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == '+')
{
dfs(0, i, j);
return 0;
}
}
}
return 0;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...