2017年4月12日 星期三

[LeetCode] 130. Surrounded Regions

轉自LeetCode

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
<Solution>
這題是滿標準的 DFS 題目,只不過從哪裡開始做 DFS 要慎選一下

題目是要求找到被環繞,即上下左右被 X 包圍的區塊

如果直接去找被包圍的區塊,然後判斷它有沒有連到邊緣,這樣會複雜許多

反之,直接找到開放的區塊,也就是從在四條邊緣上的O開始找起

把開放區塊轉換成另一個字元,最後剩下來的O就是要變成X的

code 如下
c++

kotlin

沒有留言:

張貼留言