Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1421

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1421

Tic-Tac-Toe?

 

Maratona de Programação IME-USP Brasil

Timelimit: 3

Mickayil Romanoff received as a birthday gift a very interesting game: a tridimensional tic-tac-toe. The game is made of n x n pins, arranged in a square matrix. Each pin has a space to receive n balls of the colors white and blue. As in the traditional tic-tac-toe, the goal of the game is to get a complete sequence (in any direction) of n balls of the same color. Notice that, when you put a ball in one of the pins, it necessarily falls until it reaches the first empty level, because of the gravity.

After several games, Mickayil noticed that he couldn’t realize if someone had won. Your task in this problem is to help Mickayil, writing a program that receives a match and determines who won.

 

Input

 

Several instances are given. The first line of each instance contains a dimension 0 ≤ n ≤ 30 of the matrix. Next, in each one of the next n3 lines are given, alternately, the positions where the players are putting the balls in, starting by the white player. Each position is given by the pin where the ball was placed, in other words, a pair (i, j), where i, j ∈ {1, …, n}. The input ends with a zero.

 

Output

 

You must print a header indicating the instance number that you are on (Instancia h) and in the next line the message that the player won the match (Branco ganhou or Azul ganhou), or if the game tied (Empate). Remember that the first player who got a complete sequence wins the match. A blank line must be printed after each test output instance.

 

 

 

Sample Input Sample Output
2
1 1
1 2
1 2
2 1
2 2
2 1
2 2
1 1
0
Instancia 1
Branco ganhou

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i  < = b; ++i)
#define RFOR(i, b, a) for (int i = b; i >= a; --i)
#define REP(i, N) for (int i = 0; i  <  N; ++i)
#define MAX 110
#define pb push_back
#define mp make_pair

using namespace std;

const double pi = acos(-1.0);
const double EPS = 1e-9;

struct pt;
typedef pair < pt, pt> line;
typedef vector<pt> polygon;
typedef pair < pt, int> ddi;
typedef pair dd;

int cmp(double a, double b = 0.0)
{
    if (fabs(a - b)  <  EPS)
        return 0;
    return a > b ? 1 : -1;
}

int velha[40][40][40], pos[40][40], player = 1;

int verificaJogo(int n, int i, int a, int b, int c)
{
    int x = 0, y = n - 1, dPrinc = 0, dSecun = 0, vert = 0, horiz = 0;
    for (int k = 0; k  <  n; ++k) {
        /* Verifica as diagonais */
        if (velha[i][k][k] == c)
            dPrinc++;

        if (velha[i][x][y] == c)
            dSecun++;
        x++, y--;

        /* Verifica a linha */
        if (velha[i][a][k] == c)
            horiz++;

        /* Verifica a coluna */
        if (velha[i][k][b] == c)
            vert++;
    }
    if (dPrinc == n)
        return c;
    else if (dSecun == n)
        return c;
    else if (vert == n)
        return c;
    else if (horiz == n)
        return c;
    return -1;
}

int main()
{
    int n, x, y, t = 0;
    while (scanf("%d", &n) && n) {
        printf("Instancia %d\n", ++t);
        for (int i = 0; i  <  n; ++i)
            for (int j = 0; j  <  n; ++j) {
                for (int k = 0; k  <  n; ++k)
                    velha[i][j][k] = -1;
                pos[i][j] = 0;
            }
        int winner = -1;
        for (int i = 0; i  <  n * n * n; ++i) {
            scanf("%d %d", &x, &y);
            player = !player;
            if (winner != -1)
                continue;
            if (player)
                velha[pos[x - 1][y - 1]][x - 1][y - 1] = player;
            else
                velha[pos[x - 1][y - 1]][x - 1][y - 1] = player;
            winner = verificaJogo(n, pos[x - 1][y - 1]++, x - 1, y - 1, player);
        }
        if (winner == -1)
            puts("Empate\n");
        else
            printf("%s", (winner) ? "Branco ganhou\n\n" : "Azul ganhou\n\n");
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2
1 1
1 2
1 2
2 1
2 2
2 1
2 2
1 1
0

Output

x
+
cmd
Instancia 1
Branco ganhou
Advertisements

Demonstration


Previous
#1419 Beecrowd Online Judge Solution 1419 Bakugan Solution in C, C++, Java, Js and Python
Next
#1426 Beecrowd Online Judge Solution 1426 Add Bricks in The Wall Solution in C, C++, Java, Js and Python