Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1421
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1421
Tic-Tac-Toe?
BrasilTimelimit: 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;
}
Input
1 1
1 2
1 2
2 1
2 2
2 1
2 2
1 1
0
Output
Branco ganhou