CF1749E Cactus Wall 题解 Forget_Everything · 2023-11-17 23:07:32 · 题解 解题思路 考虑建图，很容易想到放置后的仙人掌需满足存在一条从第一列到第 m 列的路径，那么我们的最优答案就是一条从第 1 列到第 m 列的最短路，其中，到达一个已经有仙人掌的点花费 0 的代价，到达一个不存在仙人掌的点花费 1 的代价。我们可以使用双端队列 bfs，即边权为 0 的放前面，边权为 1 的放后面。 注意事项 在建图的时候需要注意，只能斜着走且不能到达和仙人掌相邻的格子； 多测不清空，爆零两行泪；清空不规范，TLE 总相伴。 以上是本题的思路，代码就不贴了。