解题思路
本题可以转化为在一个网格上的状态搜索问题。猎手和幻影的初始位置已知,每次猎手移动一个方向,幻影同时向相反方向移动一格。猎手不能踏入陷阱,幻影一旦踏入陷阱即被消灭。我们需要统计存在合法移动序列使得幻影能被消灭的陷阱总数。
由于猎手和幻影同步移动,我们可以使用**广度优先搜索(BFS)**遍历所有可能的状态。具体思路如下:
- 状态表示:用一个四元组 (rh,ch,rp,cp) 表示猎手在 (rh,ch),幻影在 (rp,cp)。行和列均采用 0 起始的索引以方便编程。
猎手初始位置:(2n−1,2m−1);幻影初始位置:(2n,2m)。