Problem: second_second_friend (2022 quals)

**Note: The only difference between this problem and [problem B1](https://www.facebook.com/codingcompetitions/hacker-cup/2022/qualification-round/problems/B1) is that here, scenes are larger and may contain rocks.**

Boss Rob painted a beautiful scene on a 2D canvas of \(R\) rows by \(C\) columns, containing zero or more happy little trees **and zero or more rocks.**

To make sure none of his trees are lonely, Rob would like you to add as many trees as you'd like (possibly \(0\)) to empty spaces so that each tree in the final painting has at least two tree *friends*, that is, two trees which are each adjacent to it (directly to its north, south, east, or west). If there are multiple solutions, you may print any one of them. 


# Constraints

\(1 \leq T \leq 80\)
\(1 \leq R, C \leq \mathbf{3{,}000}\)


# Input Format

Input begins with an integer \(T\), the number of test cases. For each case, there is first a line containing two space-separated integers, \(R\) and \(C\). Then, \(R\) lines follow, each of which contains \(C\) characters, either "`.`" (an empty space), "`^`" (a tree), **or "`#`" (a rock)**, representing the initial painting.


# Output Format

For the \(i\)th case, print "`Case #i:` ", followed by "`Possible`" and \(R\) lines of \(C\) characters each representing the final painting (if a solution exists), otherwise "`Impossible`".


# Sample Explanation

In the first case (depicted below), we could add two tree friends to either side of the middle tree, but they themselves would each only have one tree friend. Therefore, it's impossible to get two friends for each tree in the final painting.

{{PHOTO_ID:604840697695882|WIDTH:295}}

In the second case, there are no trees in the initial painting, so the condition of two friends for each tree is already satisfied.

In the third case, one possible solution is depicted below.

{{PHOTO_ID:749016109740997|WIDTH:700}}


Sample input:
3
1 3
.^.
3 1
.
#
#
4 4
..^.
.#^#
....
...^


Sample output:
Case #1: Impossible
Case #2: Possible
.
#
#
Case #3: Possible
^^^.
^#^#
^^^^
..^^


Solution: The same impossible cases apply as before: one row or one column, with at least one tree.

Otherwise, we'll start by marking all non-rock cells as "good." Next, we'll mark all spaces with \(0\) or \(1\) good neighbors as "bad" in \(\mathcal{O}(RC)\) time. We can then run a breadth-first search from these initial bad spaces. At each BFS step, we check if a space is marked good, but currently has fewer than \(2\) good neighbors. If so, mark it as bad and enqueue its neighbors so they can later be checked for consistency, as each neighbor will now have one fewer good neighbor. When the BFS terminates, all good/bad markings will be consistent. Finally, we check if any tree in the original input is marked bad, in which case the answer is "`Impossible`". Otherwise, we can output a tree for all spaces marked good.

It can be observed that for every BFS step that branches, we are converting a different good cell to bad, of which there can be at most \(R * C\). Thus the BFS must terminate, and in worst-case running time \(\mathcal{O}(RC)\).

[See David Harmeyer's solution video here.](https://youtu.be/aC0n8sB2BLs)


Code: #include <iostream>
#include <queue>
#include <utility>
using namespace std;

const int LIM = 3005;

int R, C;
char G[LIM][LIM];
bool bad[LIM][LIM];

inline bool good(int i, int j) {
  return i >= 0 && i < R && j >= 0 && j < C && G[i][j] != '#' && !bad[i][j];
}

inline int num_good_adj(int i, int j) {
  return good(i - 1, j) + good(i + 1, j) + good(i, j - 1) + good(i, j + 1);
}

void solve() {
  bool empty = true;
  cin >> R >> C;
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      cin >> G[i][j];
      empty = empty && G[i][j] != '^';
    }
  }
  if (!empty && (R < 2 || C < 2)) {
    cout << "Impossible" << endl;
    return;
  }
  queue<pair<int, int>> q;
  memset(bad, false, sizeof bad);
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      if (num_good_adj(i, j) < 2) {
        q.push({i, j});
      }
    }
  }
  while (!q.empty()) {
    auto [i, j] = q.front();
    q.pop();
    if (good(i, j) && num_good_adj(i, j) < 2) {
      if (G[i][j] == '^') {
        cout << "Impossible" << endl;
        return;
      }
      bad[i][j] = true;
      q.push({i - 1, j});
      q.push({i + 1, j});
      q.push({i, j - 1});
      q.push({i, j + 1});
    }
  }
  cout << "Possible" << endl;
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      if (G[i][j] == '.' && !bad[i][j]) {
        cout << '^';
      } else {
        cout << G[i][j];
      }
    }
    cout << endl;
  }
}

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