幻想城堡 题解

思路

把特殊格子视为“必败目标”：棋子一旦到达它，上一位移动者已经获胜。对于普通格子，只要同行右侧或同列下方存在一个必败目标，它就是必胜格；若两处都不存在，它就是新的必败格。

从右下角向左上角考察必败格的边界。设当前指针为 $(x,y)$：

• 若 $(x,y)$ 本身是特殊格子，它作为必败目标，同时封住当前行与当前列，指针左上移动；
• 若第 $x$ 行在 $y$ 右侧有特殊格子，这一行当前位置必胜，指针上移；
• 否则若第 $y$ 列在 $x$ 下方有特殊格子，这一列当前位置必胜，指针左移；
• 否则 $(x,y)$ 是新的普通必败格，指针左上移动。

新发现的普通必败格都位于这条单调边界上；指针左上移动后，不会再次与它同行或同列。因此后续查询只需关注输入的特殊格子。

做法

子任务 1 对每个格子递归枚举所有向右、向下的后继，直接计算胜负，复杂度 $O(NM(N+M))$。

子任务 2 从右下向左上扫描整个棋盘，分别记录每一行右侧和每一列下方是否已经出现必败目标，复杂度 $O(NM)$。

满分做法预处理每行特殊格子的最大列号与每列特殊格子的最大行号，再执行上述单调指针。用哈希集合判断当前格是否特殊，总共至多移动 $N+M$ 次。

最后，若边界访问到 $(1,1)$ 且判定它为普通必败格，则 Bhinneka 获胜；否则 Chaneka 获胜。

复杂度

• 子任务 1：时间 $O(NM(N+M))$，空间 $O(NM)$；
• 子任务 2：时间 $O(NM)$，空间 $O(NM)$；
• 满分算法：时间 $O(N+M+K)$，空间 $O(N+M+K)$。