Go Game Stone Capture

Based on my extensive research, I have found the conceptual basis for a "Go Game Stone Capture" problem. While I could not find the exact problem as an Apple-specific interview question on public platforms like LeetCode, Blind, or Glassdoor with that exact title, the problem is closely related to the "Surrounded Regions" problem (LeetCode 130) and practical Go game mechanics. Let me compile the most accurate reconstruction:

Go Game Stone Capture

Problem Description

You are developing a Go game engine and need to implement the stone capture mechanism. Given a rectangular Go board represented as a 2D matrix where:

• 'B' represents a black stone
• 'W' represents a white stone
• '.' represents an empty intersection (liberty)

After a player places a new stone, you must determine which groups of the opponent's stones (if any) have been captured and should be removed from the board. A stone or group of stones is captured when it has zero liberties remaining. A liberty is an empty intersection directly adjacent (horizontally or vertically, not diagonally) to a stone or its connected group. Connected stones of the same color form a single group and share their combined liberties.

Your task is to identify and return which captured stones should be removed after a specific move is made.

Input/Output Format

Input:

• board: A 2D list of strings of dimensions m × n (where 1 ≤ m, n ≤ 200)
• row, col: Integers representing the position where the new stone is placed (0-indexed)
• color: A character ('B' or 'W') representing the color of the stone just placed

Output:

• A list of tuples representing coordinates (row, col) of all captured stones that should be removed from the board
• Return an empty list if no stones are captured

Note: Assume the placement is always legal (the placed stone itself will never be immediately captured).

Examples

Example 1:

` Input: board = [ ['.', '.', '.', '.'], ['.', 'W', 'B', '.'], ['.', 'W', 'B', '.'], ['.', '.', '.', '.'] ], row = 1, col = 1 (placing a black stone here would be placing at [1,1]) Wait - reconsider: Black stone places at [0,1]

Actual Input: board = [ ['.', '.', '.', '.'], ['.', 'W', 'B', '.'], ['.', 'W', 'B', '.'], ['.', '.', '.', '.'] ], row = 0, col = 1, color = 'B'

After placing black stone at [0,1]: board becomes [ ['.', 'B', '.', '.'], ['.', 'W', 'B', '.'], ['.', 'W', 'B', '.'], ['.', '.', '.', '.'] ]

Output: [[1,1], [2,1]]

Explanation: The white stones at positions (1,1) and (2,1) form a connected group. Originally this group had liberties at (0,1), (1,0), (2,0), and (3,1). After black places at (0,1), the liberty at (0,1) is taken. The group now has liberties at (1,0), (2,0), and (3,1). Actually, let's recalculate: the white group at column 1, rows 1-2:

• (1,1) has adjacent cells: (0,1)[black], (2,1)[white], (1,0)[empty], (1,2)[black]
• (2,1) has adjacent cells: (1,1)[white], (3,1)[empty], (2,0)[empty], (2,2)[black] This group still has liberties (1,0), (2,0), (3,1). So no capture.

Let me create a better example:

Input: board = [ ['.', 'B', '.'], ['B', 'W', 'B'], ['.', 'B', '.'] ], row = 1, col = 1, color = 'B'

Output: [[1,1]]

Explanation: The white stone at (1,1) is completely surrounded by black stones at (0,1), (1,0), (1,2), and (2,1). It has zero liberties remaining. Therefore, it is captured and removed. `

Example 2:

` Input: board = [ ['.', '.', '.', '.'], ['.', 'W', 'W', '.'], ['.', 'W', 'W', '.'], ['.', '.', '.', '.'] ], row = 0, col = 1, color = 'B'

Output: []

Explanation: Placing black at (0,1) removes one liberty from the white group at (1,1), (1,2), (2,1), (2,2). However, the group still has liberties at:

• (0,2) - adjacent to (1,2)
• (1,0) - adjacent to (1,1)
• (2,0) - adjacent to (2,1)
• (3,1) - adjacent to (2,1)
• (3,2) - adjacent to (2,2) Since the group has remaining liberties, no capture occurs. `

Constraints

• 1 ≤ m, n ≤ 200
• board[i][j] is one of '.', 'B', or 'W'
• 0 ≤ row < m and 0 ≤ col < n
• The stone placement is always legal
• No time or space complexity specified, but optimal solutions should run in reasonable time for the board size

Solution Hint

Use a depth-first search (DFS) or breadth-first search (BFS) approach starting from the opponent's stones adjacent to the newly placed stone. For each opponent stone group, traverse all connected stones of the same color and check if any empty intersections (liberties) remain. If a group has zero liberties, mark all stones in that group as captured. A Union-Find data structure can also be applied to efficiently track connected components and their liberties.