LeetCode.Surrounded Regions

Problem:

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.

Example:

 

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

 

-Summary-

Solved by BFS using Queue

 

1. If the board is empty or row and column lengths is less than equal to 2, we just return to the original board

2. First, we will put all the border element to the queue to check if it is "O".

3. If it is "O", we change to "N" to change "O" later. (we add to the queue for surrounding element as well if current position is "O".)

4. Once the loop is over and change all border "O" and connected "O" to "N", now we change all "O" to "X" since they are apart from the border "O".

5. change back to the "N" to "O".

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]