问题分析

我们需要判断是否存在一种移动序列，使得：

• 所有可通过格子都被水平移动覆盖过（涂黄色）
• 所有可通过格子都被垂直移动覆盖过（涂蓝色）

核心思路

关键观察

1. 水平移动会覆盖整行连续可通过区域
2. 垂直移动会覆盖整列连续可通过区域
3. 每个格子必须同时被水平和垂直移动覆盖

问题转化

将问题转化为2-SAT问题：

• 对每个可通过格子，定义两个变量：
  • $H_{ij}$：该格子被水平移动覆盖
  • $V_{ij}$：该格子被垂直移动覆盖
• 约束条件：$H_{ij} \land V_{ij}$ 必须为真

算法步骤

1. 预处理连通段

   • 扫描每行，找出所有连续的可通过段（行段）
   • 扫描每列，找出所有连续的可通过段（列段）

2. 构建依赖图

   • 每个行段对应一个水平覆盖选择
   • 每个列段对应一个垂直覆盖选择
   • 建立逻辑关系：选择某个行段 → 该段内所有格子$H$为真

3. 2-SAT求解

   • 使用Tarjan算法求强连通分量
   • 检查是否存在矛盾

可行性判断

返回1当且仅当：

• 每个可通过格子都至少在一个行段和一个列段中
• 2-SAT问题有解

复杂度

• 时间复杂度：$O(NM)$
• 空间复杂度：$O(NM)$

这种解法将复杂的移动规则转化为经典的图论问题，从而高效求解。