Loading...
Loading...
Loading...
Arjun and his sister play a board game on a grid of r rows and c columns. Each cell holds Arjun's stone X or is open, O.
Open cells that share a side (up, down, left or right) form a patch. A patch is captured when none of its cells is on the edge of the board: it is enclosed by stones. Every captured cell becomes X. A patch with at least one cell on the edge stays open.
Print the board after all captures.
X or O, with no spaces.X or O.Example 1
Input
4 4 XXXX XOOX XXOX XOXX
Output
XXXX XXXX XXXX XOXX
The three middle O cells are enclosed and become X. The O on the bottom edge stays.
Example 2
Input
3 4 XOXX XOOX XXXX
Output
XOXX XOOX XXXX
The patch reaches the top edge through its first cell, so nothing is captured.
Try the problem first. Open one hint at a time.
Turn the question around: which open cells are safe? A cell is safe when its patch reaches the edge.
Start from every O on the four edges and visit all open cells joined to them. Mark those as safe.
Every O that is not marked safe is enclosed, so it becomes X.
Use a queue instead of a method that calls itself, because a 200 × 200 board can hold one huge patch.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor