CF1201E2 题解

· · 题解

orz Charlie/bx.

考虑对棋盘染色,那么马移动到的格子和原来的格子异色。

进而发现若两个马初始异色,那么只有白马可以吃黑马,否则只有黑马可以吃白马。

下面只讨论初始异色的情况,同色是对称的。下文令 W, B, T_W, T_B 分别为白马起点,黑马起点,白马终点,黑马终点。

考虑若白马能比黑马早到终点,即 \text{dis}(W, T_W) \le \text{dis}(B, T_B),那么白马直接不管黑马冲到终点就行了,反正黑马也吃不掉它。

否则白马比速度肯定比不过了,就要想办法吃掉黑马。发现如果白马能比黑马早到 T_B 白马才有可能吃掉黑马。因为题目说另一只马到了终点再吃也算吃掉,所以这里的早到定义为 \text{dis}(W, T_B) \le \text{dis}(B, T_B) + 1

那么白马到了 T_B 后如果还没吃掉黑马,那么此时白马和黑马的距离一定至少为 2(因为两只马此时位置同色)。黑马肯定不能移动使得它与白马的距离为 1,否则白马就吃掉它了。所以黑马只能移动使得它与白马的距离为 3。又因为 \text{dis}(T_W, T_B) = 3,所以白马直接冲到终点就结束了。

如果不满足 \text{dis}(W, T_B) \le \text{dis}(B, T_B) + 1 那么白马无法吃掉黑马。这种情况黑马直接冲到终点就能赢,不用管白马。

直接模拟上面的分析过程即可。实现时需要以 W, B 为起点跑最短路并且记录一下前驱。

code