Practice/Meta/Go Scoreboard

Go Scoreboard

CodingOptional

Problem

You are building a scoring system for a simplified territory control board game. The game is played on a 2D grid where each cell can be:

• Empty (represented by '')
• Occupied by white ('w')
• Occupied by black ('b')

The scoring rules are:

1. Each player's score equals the total number of their pieces on the board
2. However, if a connected group of pieces is completely surrounded by the opponent's pieces (with no path to an empty cell), that group scores 0 points
3. The player with the higher score wins

Your task is to implement a function that calculates the final score and determines the winner.

Requirements

1. Implement calculateScore(board) that returns a string describing the outcome
2. A group is "connected" if pieces can reach each other through adjacent cells (up, down, left, right - no diagonals)
3. A group is "captured" if it has no adjacent empty cells and is completely surrounded by opponent pieces
4. Return format: "White wins with X points", "Black wins with X points", or "Tie at X points each"
5. Follow-up: Implement findBestMove(board) that returns the coordinates (row, col) of the empty cell where white should place a piece to maximize their score gain

Constraints

• 1 ≤ board size ≤ 20 × 20
• The board contains only '', 'w', or 'b'
• Time complexity should be O(n × m) where n and m are board dimensions
• Space complexity should be O(n × m) for tracking visited cells

Examples

Example 1:

Input: [ ['w', 'w', ''], ['w', '', ''], ['', '', 'b'] ] Output: "White wins with 4 points" Explanation: White has 3 pieces (all connected with access to empty cells = 3 points). Black has 1 piece (with access to empty cells = 1 point). Wait, let me recalculate: White has 3 connected pieces, Black has 1 piece. Both have access to empty cells, so white scores 3, black scores 1. White wins with 3 points.

Example 2:

Input: [ ['b', 'b', 'b'], ['b', 'w', 'b'], ['b', 'b', 'b'] ] Output: "Black wins with 8 points" Explanation: The white piece in the center is completely surrounded by black with no adjacent empty cells, so it scores 0 points. Black has 8 pieces with access to the board edges (considered free), scoring 8 points.

Example 3:

Input: [ ['w', 'w', '', 'b', 'b'], ['w', '', '', '', 'b'], ['', '', 'w', 'w', ''], ['b', '', 'w', '', ''], ['b', 'b', '', '', ''] ] Output: "Black wins with 7 points" Explanation: All groups have access to empty cells. White has 6 pieces, black has 7 pieces. Black wins.