在输入中，我们正在键入一个大小为8x8的棋盘，在该棋盘上，“K”代表骑士，“P”（最少1个，最多8个）代表兵，而“.”则代表空格。因此，我知道只需要使用一枚兵就可以从骑士的初始位置到达兵的位置，但是如果有八个兵呢？当然，我可以运行八个BFS，但那样效率非常低下。有没有比运行八个BFS更高效的方法来找到在棋盘上消灭所有兵所需的最小步数呢？
在一个国际象棋棋盘上，给定骑士的位置和一些兵的位置，骑士最少需要跳多少次才能杀死所有兵？
3
- Geir
2
最小生成树？ - T D Nguyen
1这个问题是旅行商问题，由于状态数量较少（8），您可以使用位掩码技术获取时间复杂度为O(nn2^n)的解决方案，其中n <= 8。 - Pham Trung
1个回答
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接