「CEOI2024」玩具谜题 题解

题目大意

有一个 $H \times W$ 的网格，上面有一个由两部分组成的金属物体：

• 横向部分：$1$ 行 $K$ 列
• 纵向部分：$L$ 行 $1$ 列

两部分必须始终重叠在一个方格上。网格中有障碍物 X 和目标格子 *。要求判断能否将金属物体移动到目标位置。

解题思路

状态表示

关键观察：两个长条的相对位置可以由它们的交叉点 $(x, y)$ 唯一确定，其中：

• $x$ 是纵向部分的行坐标（对应代码中的 x）
• $y$ 是横向部分的列坐标（对应代码中的 y）

在代码中，状态 $(sx, sy)$ 表示：

• $sx = x_h$（横向部分所在行）
• $sy = y_v$（纵向部分所在列）

可行性预处理

1. 长条位置约束

• limx[i]：当交叉点的行坐标为 $i$ 时，纵向部分可能占据的行范围
• limy[j]：当交叉点的列坐标为 $j$ 时，横向部分可能占据的列范围

2. 障碍物检查

• f[i][j]：从 $(i, j)$ 开始向右放置长度为 $K$ 的横向部分是否合法（不碰到障碍物和边界）
• g[j][i]：从 $(i, j)$ 开始向下放置长度为 $L$ 的纵向部分是否合法

深度优先搜索

从初始交叉点 $(sx, sy)$ 开始 DFS，检查四个方向的移动：

横向移动（改变行坐标）：

f[0] = limy[y];  // 可能的列范围
f[0] &= f[xx];   // 新行的横向可行性  
f[0] &= f[x];    // 原行的横向可行性

检查新位置 $(xx, y)$ 是否合法。

纵向移动（改变列坐标）：

f[0] = limx[x];  // 可能的行范围
f[0] &= g[yy];   // 新列的纵向可行性
f[0] &= g[y];    // 原列的纵向可行性

检查新位置 $(x, yy)$ 是否合法。

代码详细注释

#include <bits/stdc++.h>
using namespace std;
const int N = 1505;
char mp[N][N];
int n, m, k, l, xh, yh, xv, yv, sx, sy, ex, ey; // k hor, l ver
bitset<N> f[N], g[N], vis[N], limx[N], limy[N]; // hor:f[i][j], ver:g[j][i]

void dfs(int x, int y) {
    if (x == ex && y == ey) {  // 到达目标位置
        cout << "YES";
        exit(0);
    }

    vis[x][y] = 1;  // 标记已访问

    // 横向移动：改变行坐标x
    for (int kx : {-1, 1}) {  // 上下移动
        int xx = x + kx;
        if (xx >= 1 && xx <= n) {
            f[0] = limy[y];  // 当前列y允许的横向部分位置
            f[0] &= f[xx];   // 新行xx的横向可行性
            f[0] &= f[x];    // 原行x的横向可行性
            
            // 如果存在可行的列位置且新格子不是障碍物
            if (!vis[xx][y] && mp[xx][y] != 'X' && f[0].count())
                dfs(xx, y);
        }
    }

    // 纵向移动：改变列坐标y  
    for (int ky : {-1, 1}) {  // 左右移动
        int yy = y + ky;
        if (yy >= 1 && yy <= m) {
            f[0] = limx[x];  // 当前行x允许的纵向部分位置
            f[0] &= g[yy];   // 新列yy的纵向可行性
            f[0] &= g[y];    // 原列y的纵向可行性
            
            // 如果存在可行的行位置且新格子不是障碍物
            if (!vis[x][yy] && mp[x][yy] != 'X' && f[0].count())
                dfs(x, yy);
        }
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> m >> n >> k >> l;  // 注意输入顺序：W,H,K,L
    cin >> yh >> xh >> yv >> xv;
    ++yh, ++xh, ++yv, ++xv;  // 转换为1-indexed
    sx = xh, sy = yv;  // 初始交叉点：横向部分的行，纵向部分的列

    // 预处理limx：对于每个行i，记录纵向部分可能占据的行范围
    for (int i = 1; i <= n; ++i) {
        for (int j = max(1, i - l + 1); j <= i; ++j)
            limx[i][j] = 1;  // 纵向部分可以覆盖从j到j+l-1行，包含i行
    }

    // 预处理limy：对于每个列j，记录横向部分可能占据的列范围  
    for (int j = 1; j <= m; ++j) {
        for (int i = max(1, j - k + 1); i <= j; ++i)
            limy[j][i] = 1;  // 横向部分可以覆盖从i到i+k-1列，包含j列
    }

    // 读入网格
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> mp[i][j];
            if (mp[i][j] == '*')
                ex = i, ey = j;  // 记录目标位置
        }
    }

    // 预处理f：横向部分可行性
    for (int i = 1; i <= n; ++i) {
        int lst = m + 1;  // 右侧最近的障碍物位置
        for (int j = m; j >= 1; --j) {
            if (mp[i][j] == 'X')
                lst = j;  // 更新障碍物位置
            // 检查从j开始长度为k的横向部分是否合法
            f[i][j] = (lst >= j + k);  // 最近障碍物在范围之外
        }
    }

    // 预处理g：纵向部分可行性  
    for (int j = 1; j <= m; ++j) {
        int lst = n + 1;  // 下方最近的障碍物位置
        for (int i = n; i >= 1; --i) {
            if (mp[i][j] == 'X')
                lst = i;  // 更新障碍物位置
            // 检查从i开始长度为l的纵向部分是否合法
            g[j][i] = (lst >= i + l);  // 最近障碍物在范围之外
        }
    }

    dfs(sx, sy);  // 从初始交叉点开始搜索
    cout << "NO";  // 搜索完成未找到解
    return 0;
}

算法复杂度

• 时间复杂度：$O(H \times W)$，每个状态最多访问一次
• 空间复杂度：$O(H \times W)$，用于存储访问标记和预处理信息

关键技巧

1. bitset优化：使用 bitset 快速进行位运算，检查多个位置的可行性
2. 逆向预处理：从右到左、从下到上预处理障碍物信息
3. 状态压缩：用交叉点坐标表示整个配置状态
4. 可行性剪枝：在移动前检查新位置的合法性，避免无效搜索

该解法充分利用了题目的特性，通过巧妙的预处理和状态表示，在 $1500 \times 1500$ 的大网格上高效解决了问题。