Sealed Territories
MediumGraphs
Problem
In a territory board game the board is a list of equal-length strings board, where X is a wall and O is open ground.
A group of O cells (connected horizontally or vertically) is sealed when none of its cells lies on the edge of the board. Sealed groups are captured and become X. Return the board after every sealed group has been captured; groups that touch the edge stay as they are.
Example 1
- Input:
- board = ["XXXX", "XOOX", "XXOX", "XOXX"]
- Output:
- ["XXXX", "XXXX", "XXXX", "XOXX"]
The three O cells in the middle form a sealed group. The O on the bottom edge is not sealed.
Example 2
- Input:
- board = ["OO", "OO"]
- Output:
- ["OO", "OO"]
Every cell is on the edge, so nothing is captured.
Constraints
- 1 ≤ rows, cols ≤ 200
- Every row has the same length.
- board[r][c] is 'X' or 'O'
Hint
Show the first hint
Deciding for each group whether it reaches the edge is awkward. Which cells are definitely safe?
Walkthrough
How to approach it
01Clarify before coding
- Does a diagonal touch with the edge save a group? No, connectivity is 4-directional.
- Is a group with one cell on the border fully safe? Yes, the whole group survives.
- Should I return a new board? Yes, the rows are strings, so build new rows.
02Brute force
For every O cell, run a search to see whether it can reach the border; capture it if not.
Cost: O((r · c)²): a big open area makes each of the O(r · c) searches cost O(r · c).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.