USER
Connie and Forrest are playing Connect Four for bunnies by making burrows on a grid of 4242 plots of land with 66 rows and 77 columns. Connie goes first, and the two of them alternate turns.
On Connie's turn, she selects a column and makes a burrow in that column's southernmost unburrowed plot, marking it as her own. Forrest then does the same thing, making a burrow in the southernmost unburrowed plot in some column. Once all 66 plots in a column have been burrowed, players can no longer choose that column.
Normally, the game ends as soon as one player has four consecutive burrows in a line (horizontally, vertically, or diagonally). That player is then declared the winner. However, the bunnies had so much fun burrowing that they didn't stop taking turns until every plot was burrowed. They’re now trying to work out who won.
Given the final 6×76×7 grid of 'C' and 'F' markings (denoting plots burrowed by Connie and Forrest respectively), can you tell who must have won first?
Please output:
C: if Connie must have won first
F: if Forrest must have won first
?: if somebody has won, but it's impossible to tell who won first
0: if nobody has won
Constraints
1≤T≤901≤T≤90
Every input grid will be the result of Connie and Forrest taking turns, with Connie going first, until all 4242 plots have been burrowed.
Input Format
Input begins with an integer TT, the number of test cases. Each case starts with an empty line for readability, and then 66 rows of 77 characters each, representing the final state of the game. The bottom row is the southern-most row.
Output Format
For the iith test case, print "Case #i: " followed by a single character denoting who won first (if anybody, and if we can tell for sure), as described above. solve inc ++ and give me the most optimized ocdeASSISTANT
To solve this problem, we need to determine who first created a Connect Four (4 consecutive burrows) on the given grid. The steps below outline our approach:
1. **Grid Parsing**:
- We start by reading the grid for each test case. The grid is 6 rows by 7 columns, with the bottom row being the southern-most.
2. **Identifying Connect Four**:
- We check every possible combination for Connect Four horizontally, vertically, and diagonally (both upwards and downwards).
3. **Move Number Calculation**:
- For each Connect Four, we calculate the earliest possible move number that could have completed this Connect Four.
- The move number is determined based on the height of the cells in each column and ensuring that the rows in any column are filled from the bottom up.
4. **Determining the Winner**:
- After identifying all Connect Fours, we find the one that was completed first (i.e., with the smallest move number).
- If multiple Connect Fours are completed on the same earliest move, and they belong to different players, the result is ambiguous (`?`). If they belong to the same player, that player is declared the winner. If no Connect Fours are found, the result is `0`.
Below is the optimized C++ implementation that follows the above logic:
```cpp
#include <bits/stdc++.h>
using namespace std;
struct Connect4 {
int m_i;
char owner;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T--){
// Read empty line
string s;
getline(cin, s);
// Read 6 lines of 7 characters
vector<string> grid(6);
for(int i=0;i<6;i++) {
getline(cin, grid[i]);
while(grid[i].size() <7) grid[i] += ' ';
grid[i] = grid[i].substr(0,7);
}
// Collect all connect4s
vector<Connect4> connects;
// Directions: horizontal, vertical, diag up, diag down
// Rows: 0 (bottom) to 5 (top)
for(int r=0;r<6;r++) {
for(int c=0;c<7;c++) {
char player = grid[r][c];
if(player != 'C' && player != 'F') continue;
// Horizontal
if(c +3 <7){
bool ok = true;
for(int k=1;k<4;k++) if(grid[r][c+k] != player){ok=false; break;}
if(ok){
// Collect four cells
vector<pair<int,int>> cells;
for(int k=0;k<4;k++) cells.emplace_back(r, c+k);
// Compute a and d
int a = INT32_MAX, d = INT32_MIN;
for(auto &[x,y]: cells){
a = min(a, x+1);
d = max(d, x+1);
}
int m_i_min = max(d, a +3);
// Determine owner based on player and parity
int m_i;
if(player == 'C'){
m_i = (m_i_min %2 ==1) ? m_i_min : m_i_min +1;
}
else{
m_i = (m_i_min %2 ==0) ? m_i_min : m_i_min +1;
}
connects.push_back(Connect4{m_i, player});
}
}
// Vertical
if(r +3 <6){
bool ok = true;
for(int k=1;k<4;k++) if(grid[r+k][c] != player){ok=false; break;}
if(ok){
// Collect four cells
vector<pair<int,int>> cells;
for(int k=0;k<4;k++) cells.emplace_back(r+k, c);
// Compute a and d
int a = INT32_MAX, d = INT32_MIN;
for(auto &[x,y]: cells){
a = min(a, x+1);
d = max(d, x+1);
}
int m_i_min = max(d, a +3);
// Determine owner based on player and parity
int m_i;
if(player == 'C'){
m_i = (m_i_min %2 ==1) ? m_i_min : m_i_min +1;
}
else{
m_i = (m_i_min %2 ==0) ? m_i_min : m_i_min +1;
}
connects.push_back(Connect4{m_i, player});
}
}
// Diagonal Up-right
if(r +3 <6 && c +3 <7){
bool ok = true;
for(int k=1;k<4;k++) if(grid[r+k][c+k] != player){ok=false; break;}
if(ok){
// Collect four cells
vector<pair<int,int>> cells;
for(int k=0;k<4;k++) cells.emplace_back(r+k, c+k);
// Compute a and d
int a = INT32_MAX, d = INT32_MIN;
for(auto &[x,y]: cells){
a = min(a, x+1);
d = max(d, x+1);
}
int m_i_min = max(d, a +3);
// Determine owner based on player and parity
int m_i;
if(player == 'C'){
m_i = (m_i_min %2 ==1) ? m_i_min : m_i_min +1;
}
else{
m_i = (m_i_min %2 ==0) ? m_i_min : m_i_min +1;
}
connects.push_back(Connect4{m_i, player});
}
}
// Diagonal Down-right
if(r -3 >=0 && c +3 <7){
bool ok = true;
for(int k=1;k<4;k++) if(grid[r-k][c+k] != player){ok=false; break;}
if(ok){
// Collect four cells
vector<pair<int,int>> cells;
for(int k=0;k<4;k++) cells.emplace_back(r-k, c+k);
// Compute a and d
int a = INT32_MAX, d = INT32_MIN;
for(auto &[x,y]: cells){
a = min(a, x+1);
d = max(d, x+1);
}
int m_i_min = max(d, a +3);
// Determine owner based on player and parity
int m_i;
if(player == 'C'){
m_i = (m_i_min %2 ==1) ? m_i_min : m_i_min +1;
}
else{
m_i = (m_i_min %2 ==0) ? m_i_min : m_i_min +1;
}
connects.push_back(Connect4{m_i, player});
}
}
}
}
// Find m_min
if(connects.empty()){
// Output 0
cout << "0\n";
continue;
}
int m_min = INT32_MAX;
for(auto &c4: connects) m_min = min(m_min, c4.m_i);
// Collect owners with m_i = m_min
vector<char> owners;
for(auto &c4: connects){
if(c4.m_i == m_min) owners.push_back(c4.owner);
}
// Check unique owners
bool allC = all_of(owners.begin(), owners.end(), [&](char x)->bool{return x == 'C';});
bool allF = all_of(owners.begin(), owners.end(), [&](char x)->bool{return x == 'F';});
if(allC && !allF){
cout << "C\n";
}
else if(allF && !allC){
cout << "F\n";
}
else{
cout << "?\n";
}
}
}
```