← All coding problems
Surrounded Regions
mediumGraphs+20 XPTime limit 2s
The board contains X and O. A region of Os (connected up/down/left/right) is captured if it is completely surrounded by Xs — that is, none of its cells lies on the border of the board. Flip every captured region to X.
Input:
- line 1:
r c - next
rlines:ccharacters (XorO)
Output: the board after flipping, one row per line.
Constraints: 1 ≤ r, c ≤ 300.
Think about it: turn the question around — which Os survive? Exactly those connected to a border O. Flood-fill from every border O to mark survivors; flip everything else.
Sample input 1
4 4 XXXX XOOX XXOX XOXX
Sample output 1
XXXX XXXX XXXX XOXX
Sample input 2
1 1 X
Sample output 2
X
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).