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
沒有留言:
張貼留言