這道題我本來以為很容易就能用DFS做掉的，但是做了一半發(fā)現(xiàn)很難寫這個stop case. 到底什么算是region被包起來？ 上下左右都是X 那當(dāng)然是，但是如果是一連串的O外部被X包住，每個O的格子周圍不可能有4個X。 這個時候要怎么做判斷？

我大概寫了一下 但是沒寫出來。。。

看了一下discussion，發(fā)現(xiàn)好像BFS才是這道題比較好的解法。好不容易找到一個DFS的思路看看我是missng在哪。。

首先答案先check了一下邊界問題，因為top & bot row, left& right col 都是沒有X能夠圍住的。所以那里如果出現(xiàn)了O，是不能被變成X的。答案大神發(fā)現(xiàn)只要O的region是鏈接到邊界上的O的，都是不能被包住的。【這個observation太關(guān)鍵】。所以他先從邊界出發(fā)，把所有邊界O鏈接的O暫時變成Y這個字符。（保證之后不受影響，然后之后再改回來）

之后遍歷整個array, 把所有O的地方變成X，因為這些沒有鏈接到邊界上，都是被圍住的。最后再改Y回O。

BFS的解法：

”dfs, bfs, union-find都可以做, 基本思路是

從在四個邊的各個'O'開始搜索, 連在一起的'O'就是不能被包圍的, 其余的點都應(yīng)該設(shè)為'X'.

如果選擇bfs, 可以把所有邊上的所有'O'一起入隊, 同時進(jìn)行bfs“

感覺都是發(fā)現(xiàn)了邊界問題才知道怎么做。。

先把邊界上的O點放入queue里。然后set it = "V"

他這里對邊界的處理非常的小心。第二次的loop，他就從i=1開始，到height-2就停了。為了避免重復(fù)count。

然后進(jìn)入BFS，按最早進(jìn)Queue的先pop處理。 每次pop出一個node，就把上下左右是O的全部先變成‘v’， 然后把該位置放入queue里。等一會再pop出來 重復(fù)這個操作。這一步是為了把所有連接邊界的為O的地方全部暫時變成'V'， 然后保證之后的操作不影響他們。

BFS 做好以后，把board里所有還是"O"的地方變成“X”。