# Tic Tac Toe Codechef Solution

## Tic Tac Toe Solution Problem Code: TICTACTO

Two drunken players Alice and Bob are playing a modified version of Tic-Tac-Toe.

Initially, there is a N×MN×M empty grid.

Alice and Bob take alternate turns starting with Alice. In her turn, Alice chooses an empty cell on the board and puts a `"A"` on the chosen cell. In Bob’s turn, he chooses an empty cell and puts a `"B"` on the chosen cell.

The player who first gets any K×KK×K subgrid completely filled with his/her initial wins the game. By a K×KK×K subgrid, we mean the intersection of KK consecutive rows and KK consecutive columns. The players do not stop making turns after one of them wins and they play all N⋅MN⋅M turns until the grid is filled.

You are given the sequence of moves played by each player (The cell selected by the player in his/her turn). You have to output the winner of the game or report that there is no winner.

### Input

• The first line contains an integer TT, the number of test cases. Then the test cases follow.
• The first line of each test case contains three integers NN, MM, KK.
• Each of the next N⋅MN⋅M lines contains two integers XX, YY (the row and column of the cell chosen by the player with the current turn)

### Output

For each test case, output `"Alice"` if Alice wins the game or `"Bob"` if Bob wins the game or `"Draw"` if no one wins.

### Constraints

• 1≤T≤1051≤T≤105
• 1≤N,M≤10001≤N,M≤1000
• 1≤K≤min(N,M)1≤K≤min(N,M)
• 1≤X≤N1≤X≤N
• 1≤Y≤M1≤Y≤M
• The sum of N⋅MN⋅M over all test cases does not exceed 106106.

Subtask 1 (10 points): 1≤N≤10, 1≤M≤101≤N≤10, 1≤M≤10

Subtask 2 (20 points): 1≤N≤50, 1≤M≤501≤N≤50, 1≤M≤50

Subtask 3 (70 points): Original Constraints

### Sample Input

``````1
3 4 2
1 1
3 1
1 2
2 3
2 1
2 4
3 2
3 4
1 3
3 3
2 2
1 4
``````

### Sample Output

``````Bob
``````

### Explanation

After 1010 turns of the game the state of the grid is:

``````AAA.
A.BB
BABB
``````

At this moment, Bob has achieved a subgrid of 2×22×2 with his initials while Alice has not achieved it yet so Bob is the winner.

Program:

``````#include <bits/stdc++.h>
using namespace std;
struct play{
int pos;
char per;
int val = 0;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,n,m,k;
cin>>t;
while(t--){
cin>>n>>m>>k;
play arr[n][m];
int x,y;
for(int i=0;i<n*m;i++){
cin>>x>>y;
arr[x-1][y-1].per = i%2==0 ? 'A':'B';
arr[x-1][y-1].pos = i;
}
int found = n*m;
string winner = "Draw";
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
char ch = arr[i][j].per;
if(i==0 or j==0){
arr[i][j].val = 1;
}else if(ch == arr[i-1][j-1].per and ch == arr[i-1][j].per and ch == arr[i][j-1].per){
arr[i][j].val = 1 + min({arr[i-1][j-1].val,arr[i-1][j].val,arr[i][j-1].val});
}else{
arr[i][j].val = 1;
}
}
}

for(int i=k-1;i<n;i++){
for(int j=k-1;j<m;j++){
if(arr[i][j].val >= k){
char win = arr[i][j].per;
int latest = 0;
for(int I = i-k+1;I<=i;I++){
for(int J =j-k+1;J<=j;J++){
latest = max(latest,arr[I][J].pos);
}
}
found = min(found,latest);
if(found == latest){
winner = (win=='B' ? "Bob":"Alice");
}
}
}
}

if(found != m*n){
cout<<winner<<"\n";
}else{
cout<<"Draw\n";
}

}
return 0;
}
``````