Problem: ready_go_part_2 (2023 round2)

_This problem shares some similarities with A1, with key differences in bold._

_Atari 2600? More like Atari 2600 BCE!_

The classic board game _Go_ is a two-player game played on an \(R \times C\) board. One player places white stones while the other places black stones. On a player's turn, they may place a stone in any empty space. A curiosity of Go is that stones are placed on the intersections of grid lines rather than between the lines, so an in-progress \(5 \times 5\) game looks like this:

{{PHOTO_ID:142163805651048|WIDTH:180}}

An orthogonally contiguous set of stones of the same color is called a *group*. A group of stones is captured (and removed from the board) once no stones in the group has an adjacent empty space.

You're playing as Black and it's your turn. Given a valid board (i.e. no groups have \(0\) adjacent empty spaces), **what’s the maximum number of white stones you can capture** with a single black stone?

Here are some examples of captures. If a black stone is placed at the point marked with a triangle, a single white stone will be captured:

{{PHOTO_ID:1327337367897977|WIDTH:300}}

Here, Black can capture a group of \(3\) white stones. Note that this move is valid even though the new black stone has no adjacent empty spaces at the moment it's placed:

{{PHOTO_ID:311797128262237|WIDTH:240}}

Black can even capture multiple groups at once. Here, Black captures a group of \(2\) stones and a group of \(3\) stones:

{{PHOTO_ID:975143063563862|WIDTH:400}}

The Go board is represented as a character array \(A\) where \(A_{i, j}\) is one of:
* `B` for a black stone
* `W` for a white stone
* `.` for an empty space


# Constraints

\(1 \leq T \leq 150\)
\(1 \leq R, C \leq \textbf{3{,}000}\)
\(A_{i, j} \in \{\)'`.`', '`B`', '`W`'\(\}\)


# Input Format

Input begins with an integer \(T\), the number of test cases. Each case begins with a line containing two integers \(R\) and \(C\). Then, \(R\) lines follow, the \(i\)th of which contains \(C\) characters \(A_{i, 1}\) through \(A_{i,C}\).


# Output Format

For the \(i\)th test case, print "`Case #i:` " followed by a single integer, the maximum number of white stones you can capture on your turn.


# Sample Explanation

In the first case, Black can capture 3 white stones by playing in the bottom-right corner.

In the second case, there are no white stones that can be captured.

In the third case, Black can capture both white groups at once, for a total of 6 + 3 = 9 white stones.

In the fourth case, there are 6 different white stones that can be captured, but Black can capture at most 4 of them at once (by playing in the center of the board).



Sample input:
4
4 4
W...
B.BB
.BWW
.BW.
5 5
W...W
.W.W.
BBWBB
.W.W.
W...W
5 5
B..B.
WBBWB
W.WWB
WWBB.
WWB..
5 5
.....
WB.BW
BW.WB
BWBWB
.B.B.


Sample output:
Case #1: 3
Case #2: 0
Case #3: 9
Case #4: 4


Solution: We can augment our solution to part 1 with a bit more information to solve part 2. Additionally, now that the bounds are larger, depth-first search solutions will need to be more careful about stack size. Breadth-first solutions won't have this problem.

We'll build up a table, \(\text{captured}(i, j)\), the number of white stones you can capture if you play a black stone at \((i, j)\). Initially every entry in this table is \(0\).

When you run your search to find all of the white stones in a given group, keep track of the total number of white stones in the group. Call this \(K\). If and only if this group turns out to have exactly \(1\) adjacent empty space at \((i, j)\), then increment \(\text{captured}(i, j)\) by \(K\), indicating that we'll capture these \(K\) stones if we play at \((i, j)\). If multiple white groups share the same single adjacent empty space, we'll be summing the sizes of all of those groups.

At the end, your answer is the maximum value in \(\text{captured}\). This solution still has a time complexity of \(\mathcal{O}(R * C\)).


Code: #include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <utility>
using namespace std;

vector<vector<char>> A;
vector<vector<bool>> visit;
set<pair<int, int>> empty_adj;
map<pair<int, int>, int> captured;

int rec(int r, int c) {
  visit[r][c] = true;
  int cnt = 1;
  for (auto [r2, c2] : {pair{r - 1, c}, {r, c - 1}, {r + 1, c}, {r, c + 1}}) {
    if (A[r2][c2] == '.') {
      empty_adj.insert({r2, c2});
    } else if (A[r2][c2] == 'W' && !visit[r2][c2]) {
      cnt += rec(r2, c2);
    }
  }
  return cnt;
}

int solve() {
  int R, C;
  cin >> R >> C;
  A.assign(R + 2, vector<char>(C + 2, 'B'));
  for (int i = 1; i <= R; i++) {
    for (int j = 1; j <= C; j++) {
      cin >> A[i][j];
    }
  }
  visit.assign(R + 2, vector<bool>(C + 2, false));
  captured.clear();
  int ans = 0;
  for (int i = 1; i <= R; i++) {
    for (int j = 1; j <= C; j++) {
      if (A[i][j] == 'W' && !visit[i][j]) {
        empty_adj.clear();
        int cnt = rec(i, j);
        if (empty_adj.size() == 1) {
          ans = max(ans, captured[*empty_adj.begin()] += cnt);
        }
      }
    }
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}