Problem: second_friend (2022 quals)

**Note: The only difference between this problem and [problem B2](https://www.facebook.com/codingcompetitions/hacker-cup/2022/qualification-round/problems/B2) is that here, scenes are smaller and do not 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.

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 85\)
\(1 \leq R, C \leq \mathbf{100}\)


# 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) or "`^`" (a tree), 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:545859687328272|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:5118404751621442|WIDTH:700}}


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


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


Solution: If a grid has only one row or one column, then it's impossible for every tree to be adjacent to two other trees, since the outermost tree(s) can only have one friend. The only exception is if the grid is initially empty, in which case the requirement is vacuously true.

Otherwise, for a grid with at least two rows and columns, notice that filling the entire grid with trees will always leave every tree with at least two friends.

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


Code: #include <iostream>
using namespace std;

const int LIM = 105;

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

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;
  }
  cout << "Possible" << endl;
  for (int i = 0; i < R; i++) {
    cout << string(C, empty ? '.' : '^') << endl;
  }
}

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