思路

问题分析

这个问题本质上是一个有依赖关系的图论问题。每个三明治被切成两个小三明治，它们之间存在复杂的依赖关系：

1. 内部依赖：同一个三明治的两个小块互相制约
2. 外部依赖：相邻三明治的小块之间存在制约

关键观察

1. 依赖关系建模

对于每个三明治 $(i,j)$，根据切割方向（N 或 Z）可以确定两个小三明治的位置关系：

• N 型切割：主对角线切割，两个小三明治分别位于左上-右下
• Z 型切割：次对角线切割，两个小三明治分别位于右上-左下

每个小三明治能否被吃掉取决于：

• 同属一个三明治的另一个小三明治是否被吃掉
• 相邻的两个小三明治（与其直角边相邻的）是否被吃掉

2. 图论转化

我们可以将每个小三明治看作图中的一个节点，依赖关系看作有向边：

• 如果 A 依赖于 B，则建立边 $B \rightarrow A$（B 必须先于 A 被吃）
• 这样问题转化为：对于每个目标三明治，找到从它开始按照依赖关系必须吃掉的最小节点数

3. 拓扑排序思想

由于依赖关系构成一个有向图，我们需要：

1. 构建完整的依赖图
2. 对于每个目标节点，进行拓扑遍历，统计必须访问的节点数
3. 如果发现环，则输出 -1

算法框架

步骤 1：节点编号

将每个三明治 $(i,j)$ 的两个小块分别编号为：

• 节点 $(i,j,0)$：第一个小块
• 节点 $(i,j,1)$：第二个小块

步骤 2：建立依赖关系

根据切割类型和相邻关系，为每个节点建立出边：

步骤 3：求解每个目标

对于每个目标三明治 $(i,j)$：

1. 从该三明治的两个小块分别开始 BFS/DFS
2. 统计必须访问的节点集合
3. 取两个小块结果的最小值作为答案
4. 如果发现环（无法拓扑排序），返回 -1

复杂度分析

• 节点数：$2 \times R \times C$（每个三明治 2 个小块）
• 边数：每个节点最多 3-4 条边，总边数 $O(RC)$
• 总复杂度：对每个目标进行遍历，最坏 $O((RC)^2)$，但通过优化可达到 $O(RC)$

优化技巧

1. 记忆化：某些节点的依赖关系可以重复利用
2. 反向思维：从可吃的小三明治开始正向传播，而不是从目标反向查找
3. 批量处理：同时计算多个目标的依赖关系

核心难点

1. 依赖关系正确建模：需要仔细分析 N 和 Z 两种切割方式下的相邻关系
2. 环检测：依赖图中可能存在环，导致某些三明治永远无法被吃掉
3. 效率优化：$400 \times 400$ 的规模需要高效的算法