CEOI2024 玩具谜题 题解

· · 题解

P10804 [CEOI 2024] 玩具谜题 题解

原题

做法

在下文中，我们将横着的块称为横块，竖着的块称为竖块，将横块与竖块重叠的位置称为交点。

题目要求我们判断能否到达终点，我们考虑横竖块之间的交点是怎样移动的。也就是说，我们需要考虑横块和竖块的移动对交点位置移动的影响。

不难发现，横块横向左右移动不会对交点的位置产生影响，同理，竖块纵向上下移动也不会产生影响。因此我们在移动交点位置的时候，只需要判断是横块纵向移动了，还是竖块横向移动了。

注意到 W,H \le 1500 的矩阵大小，在这个范围矩阵中我们可以使用广度优先搜索，在搜索过程中统计可达性。

具体的，我们首先找到交点的位置，随后枚举交点移动的四个方向。由前面的推断可知，交点横向移动是竖块移动引起的，纵向移动是横块引起的。

所以我们在搜索过程中，对每个方向判断相应块是否合法。例如向右移动时，我们就应该判断右边列障碍物能否放下竖块。

由于 H,W 同阶，这里我们统一使用 n 来表示。

暴力判断一次的复杂度为 O(n)，因此总时间复杂度为 O(n^3)，并不能通过。我们需要考虑如何快速判断移动是否合法，观察这个过程，判断的方式可以概括为：判断横向连续空间 X 是否满足 K \le X，以及纵向连续空间 Y 是否满足 L \le Y，也就是我们需要快速求出一段连续区间中空地的数量。

不难想到使用前缀和以及后缀和维护出每个位置向各个方向的连续空地长度，这样就可以在 O(1) 的时间复杂度内快速判断是否能够移动，然后进行 BFS 维护可达性，这样就做完了。

贴代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1510;
int w,h,k,l;
int pre[maxn][maxn],lst[maxn][maxn],top[maxn][maxn],dow[maxn][maxn];
#define pii pair<int,int>
#define fi first
#define se second
pii xx;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
char mmp[maxn][maxn];
bool vis[maxn][maxn];
bool bfs(pii s)
{
    queue<pii> q;
    q.push(s);
    while(!q.empty())
    {
        auto nx = q.front();
        q.pop();
        int x = nx.fi;
        int y = nx.se;
        if(mmp[x][y] == '*') return true;
        if(vis[x][y]) continue;
        vis[x][y] = 1;
        for(int i = 0;i < 4;i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(mmp[xx][yy] == '.' || mmp[xx][yy] == '*')
            {
                if(dx[i])
                {
                    if(min(lst[x][y],lst[xx][y]) + min(pre[x][y],pre[xx][y]) > k) q.push({xx,y});
                }
                else if(min(dow[x][y],dow[x][yy]) + min(top[x][y], top[x][yy]) > l) q.push({x,yy});
            }
        }
    }

    return 0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> w >> h >> k >> l;
    cin >> t >> xx.fi >> xx.se >> t;
    xx.fi++;
    xx.se++;
    for(int i = 1;i <= h;i++)
        for(int j = 1;j <= w;j++)
            cin >> mmp[i][j];
    for(int i = 1;i <= h;i++)
        for(int j = 1;j <= w;j++)
            if(mmp[i][j] != 'X')
            {
                pre[i][j] = pre[i][j - 1] + 1,
                top[i][j] = top[i - 1][j] + 1;
            }
    for(int i = h;i >= 1;i--)
        for(int j = w;j >= 1;j--)
            if(mmp[i][j] != 'X')
            {
                lst[i][j] = lst[i][j + 1] + 1,
                dow[i][j] = dow[i + 1][j] + 1;
            }
    if(bfs(xx)) cout << "YES";
    else cout << "NO";
    return 0;
}