AC代碼

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

題意：

Monocarp 想用仙人掌筑墻。他想把它建在n×m個(gè)單元大小的沙地上。

最初，田里的一些單元里有仙人掌。請注意， 仙人掌不能在彼此相鄰的單元上生長，而初始場滿足了這一限制。

Monocarp可以種植新的仙人掌（它們也必須滿足上述條件）。

他不能砍掉已經(jīng)在地上生長的任何仙人掌——他沒有斧頭，而且仙人掌對他的手來說太刺痛了。

Monocarp認(rèn)為，如果從沙地的頂行到底行沒有路徑，則墻是完整的，這樣：

路徑中的每兩個(gè)連續(xù)單元并排相鄰；

屬于該路徑的任何單元都不含有仙人掌。

你的任務(wù)是種植最少數(shù)量的仙人掌來筑墻（或報(bào)告這是不可能的）。

題解：

圖論 + 最短路徑

首先標(biāo)記已有仙人掌周邊單元(同行或者同列)，這些位置不能再放置仙人掌。

對所有非標(biāo)記單元，求其周邊單元(非同行且非同列，且不是已有仙人掌周邊單元)。

在此基礎(chǔ)上求一個(gè)從左向右的路徑，充分使用已有仙人掌單元。