Problem: xs_and_os (2021 quals)

You're playing a game against an opponent on a grid of cells with \(N\) rows and \(N\) columns. All of the cells are initially empty, and both players normally take turns placing symbols in empty cells (with one player placing **X**s and the other placing **O**s) until a row and/or column becomes entirely filled with one player's symbols (at which point the game ends with that player winning) or all of the cells have been filled without either player winning (in which case the game ends in a draw). Note that a player filling an entire diagonal with their symbols does *not* cause them to win.

This particular game is in the process of being played, with you placing **X**s and your opponent placing **O**s. The current state of the cell in the \(i\)th row from the top and \(j\)th column from the left is one of the following:

  - If \(C_{i,j}\) = `"."`, the cell is still empty
  - If \(C_{i,j}\) = `"X"`, an **X** has been placed in the cell
  - Otherwise, if \(C_{i,j}\) = `"O"`, an **O** has been placed in the cell
  
In the game's current state, both players have made an equal number of turns (in other words, the number of **X**s is the same as the number of **O**s), neither player has won yet, and the game has not yet ended in a draw (meaning that at least one cell is still empty).

Your opponent has just turned their back, giving you the opportunity to immediately place as many additional **X**s on the board as you'd like, in any set of empty cells. Determine the minimum number of additional **X**s you must place such that placing them would cause you to immediately win (due to a row and/or a column becoming entirely filled with **X**s), if this is possible at all. If it is possible, you should also determine the number of different sets of cells in which that minimum number of **X**s could be placed. Two sets of cells are considered to be different if either of them includes at least one cell which the other doesn't.

# Constraints

\(1 \le T \le 70\)
\(2 \le N \le 50\)
\(C_{i,j} \in \{\)`.`, `X`, `O`\(\}\)

The sum of \(N\) across all test cases is at most \(2{,}000\).

# Input

Input begins with an integer \(T\), the number of games you play against your opponent. For each game, there is first a line containing the integer \(N\). Then, \(N\) lines follow, the \(i\)th of which contains the \(N\) characters \(C_{i,1..N}\).

# Output

For the \(i\)th game, print a line containing "Case #i: " follow by "Impossible" if you cannot immediately win, or two integers if you can: the minimum number of additional **X**s you must place to do so, and the number of different sets of cells in which that minimum number of **X**s could be placed.


# Sample Explanation

In the first case, there's one way to place just \(1\) additional **X** and win. You can place it in the bottom-left corner (thus filling the entire left column):

```
  XO
  X.
```
  
In the second case, there are two possible ways to place \(1\) additional **X** and win:

```
  X.  XX
  XO  .O
```
  
In the third case, you'll need to place \(3\) **X**s to win, and you could choose any of the following \(6\) sets of cells to place them in:

```
  XXX  ...  ...  X..  .X.   ..X
  ...  XXX  ...  X..  .X.   ..X
  ...  ...  XXX  X..  .X.   ..X
```
  
In the fourth case, you could place \(2\) additional **X**s to form either of the following \(2\) configurations:

```
  XOX  .OX
  X..  XXX
  X.O  ..O
```
  
In the sixth case, even if you place **X**s in all \(3\) remaining empty cells, you cannot win.


Sample input:
8
2
XO
..
2
X.
.O
3
...
...
...
3
.OX
X..
..O
3
OXO
X.X
OXO
3
.XO
O.X
XO.
4
X...
.O.O
.XX.
O.XO
5
OX.OO
X.XXX
OXOOO
OXOOO
XXXX.


Sample output:
Case #1: 1 1
Case #2: 1 2
Case #3: 3 6
Case #4: 2 2
Case #5: 1 1
Case #6: Impossible
Case #7: 2 2
Case #8: 1 2


Solution: For any given row or column, if it has no **O**s and has \(k\) empty spaces, then you can win by placing \(k\) **X**s in it (filling in the empty spaces). This covers all possible optimal ways in which you might win, as you should never place additional **X**s which don't directly contribute to winning in a single row or column. The first part of the answer is therefore the minimum value of \(k\) across all such rows and columns, and it's impossible to win if there are none.

If it's possible to win, then the second part of the answer is equal to the number of distinct sets of empty cells (in which **X**s will be placed) in those minimum-\(k\) rows/columns. If the minimum \(k\) is at least 2, this is simply equal to the number of such rows/columns, as no two of them can correspond to the same set of empty cells. On the other hand, if the minimum \(k\) is 1, then the second part of the answer may be smaller than that row/column count, as filling a row and filling a column might both involve placing an **X** in the same cell as one another. Therefore, for this case, we need to compute the set of distinct single empty cells found in all rows/columns which have \(k=1\), with the second part of the answer then being the size of that set.

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


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

const int MAXN = 50, INF = 1e9;

int N;
char C[MAXN][MAXN];

void solve() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> C[i][j];
    }
  }
  int ans1 = INF, ans2;
  set<pair<int, int>> S;
  // Rows
  for (int i = 0, j; i < N; i++) {
    vector<int> empty;
    for (j = 0; j < N; j++) {
      if (C[i][j] == 'O') {
        break;
      }
      if (C[i][j] == '.') {
        empty.push_back(j);
      }
    }
    if (j == N) {
      int c = empty.size();
      if (c < ans1) {
        ans1 = c;
        ans2 = 0;
      }
      if (c == 1) {
        S.insert(make_pair(i, empty[0]));
      } else if (c == ans1) {
        ans2++;
      }
    }
  }
  // Columns
  for (int i, j = 0; j < N; j++) {
    vector<int> empty;
    for (i = 0; i < N; i++) {
      if (C[i][j] == 'O') {
        break;
      }
      if (C[i][j] == '.') {
        empty.push_back(i);
      }
    }
    if (i == N) {
      int c = empty.size();
      if (c < ans1) {
        ans1 = c;
        ans2 = 0;
      }
      if (c == 1) {
        S.insert(make_pair(empty[0], j));
      } else if (c == ans1) {
        ans2++;
      }
    }
  }
  if (ans1 == INF) {
    cout << "Impossible" << endl;
  } else {
    cout << ans1 << " " << (ans1 == 1 ? S.size() : ans2) << endl;
  }
}

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