读完题能明显感觉到博弈论气息,不妨往这方面想想。
观察一下数据范围,n,m≤10,一共只有三个棋子、先后手顺序,总状态数最高 2(nm)3,接近 2⋅106。
也就是说,我们可以直接暴力枚举所有状态,考虑博弈论的图论建模。
所有终止状态的表示是容易的,排除所有不合法状态后,我们对状态建立反图进行 BFS,同时每个点维护入度 d。
容易发现,一个必胜态的点一定被一个必败态后继更新,我们需要步数最小的必败态后继,也就是 BFS 最先找到的必败态后继;类似的,一个必败态点必须只有必胜态后继,也就是被最后一个必胜态后继更新。