AC代码

https://codeforces.com/contest/1749/submission/179160516

题意：

Monocarp 想用仙人掌筑墙。他想把它建在n×m个单元大小的沙地上。

最初，田里的一些单元里有仙人掌。请注意， 仙人掌不能在彼此相邻的单元上生长，而初始场满足了这一限制。

Monocarp可以种植新的仙人掌（它们也必须满足上述条件）。

他不能砍掉已经在地上生长的任何仙人掌——他没有斧头，而且仙人掌对他的手来说太刺痛了。

Monocarp认为，如果从沙地的顶行到底行没有路径，则墙是完整的，这样：

路径中的每两个连续单元并排相邻；

属于该路径的任何单元都不含有仙人掌。

你的任务是种植最少数量的仙人掌来筑墙（或报告这是不可能的）。

题解：

图论 + 最短路径

首先标记已有仙人掌周边单元(同行或者同列)，这些位置不能再放置仙人掌。

对所有非标记单元，求其周边单元(非同行且非同列，且不是已有仙人掌周边单元)。

在此基础上求一个从左向右的路径，充分使用已有仙人掌单元。