专栏文章

题解: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 条评论,欢迎与作者交流。

正在加载评论...