Tic Tac Toe Codechef Solution

by

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.

Subtasks

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;
}

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment

10 + 1 =