URI PROBLEMA 1206 - Desafio de São Petersburgo SOLUÇÃO EM C++

URI Online Judge | 1206

Desafio de São Petersburgo

Por Marcio T. I. Oshiro  Brasil

Timelimit: 1

A Russia sempre foi berço de grandes mestres de xadrez. Poucos sabem, mas a FIDE (Federação Internacional de Xadrez), que é o órgão máximo regulador do jogo de xadrez foi fundada em 1924, a partir de um movimento iniciado 10 anos antes no campeonato mundial da modalidade que ocorreu em São Petersburgo em 1914. Hoje, entre os 10 melhores jogadores do mundo, segundo a FIDE, três são russos.

O torneio de São Petersburgo ficou também conhecido pelas tentativas dos grandes mestres de popularização do jogo. Na época os maiores mestres (como Capablanca) foram às ruas propor desafios para as pessoas com o objetivo de interessá-las a praticar o jogo. Um desses desafios ficou conhecido como o desafio de São Petersburgo. O grande mestre montava uma situação em que as peças brancas tinham apenas o rei, e o objetivo era que a pessoa dissesse se o rei branco estava ou não em xeque mate.

Na situação descrita acima, o rei branco está em xeque mate se ele está sendo atacado e qualquer movimento que ele faça o leva para uma casa que também está sendo atacada.

O que você precisa saber sobre xadrez

Considere que inicialmente as peças do jogador preto ficam nas linhas 7 e 8 enquanto as do jogador branco iniciam nas linhas 1 e 2. Não pode haver duas peças na mesma casa. As peças consideradas no problema (peão, torre, bispo, rainha e rei) não podem passar por cima de outras peças, ou seja, se durante sua movimentação existir alguma peça no seu caminho você deve parar antes ou atacar a peça (se ela for do oponente), tomando o seu lugar. A movimentação e o ataque de cada tipo de peça são da seguinte forma:

# Peão: anda apenas uma casa para frente (em direção a linha 1) podendo atacar em qualquer uma das duas diagonais imediatamente a sua frente;
# Torre: anda/ataca quantas casas quiser ou na horizontal, ou na vertical;
# Bispo: anda/ataca quantas casas quiser na diagonal;
# Rainha: anda/ataca quantas casas quiser ou na horizontal, ou na vertical, ou na diagonal;
# Rei: anda/ataca apenas uma casa ou na horizontal, ou na vertical, ou na diagonal.

Entrada

A entrada é composta por diversas instâncias e termina com final de arquivo (EOF). A primeira linha de cada instância contém um inteiro N (2 ≤ N ≤ 10) indicando o número de peças pretas. A linha seguinte contém a descrição das posições das N peças pretas separadas por um espaço. A terceira linha contém a descrição do rei branco.

Uma descrição de uma peça de xadrez consiste em 3 caracteres. O primeiro indica se a peça é um peão (P), torre (T), bispo (B), rainha (R) ou rei (W). Note que o grande mestre não usava cavalos para facilitar para que ainda estava começando a aprender o jogo. O segundo caracter, entre ’a’ e ’h’, indica a coluna na qual a peça está e o terceiro, de ’1’ a ’8’ indica a linha.

Em nenhuma das instâncias ocorre a situação na qual o rei branco e o rei preto são adjacentes.

Saída

Para cada instância, imprima uma linha com a palavra SIM, se o rei branco está em xeque mate, ou a palavra NAO, caso contrário.

#include <cstdio>

#include <cstring>

#define MAXN 8

#define LIVRE 0

#define PECA 1

#define ATACADA 2

#define SUPORTE 3

int dx[9] = {0,1,-1,0,0,1,1,-1,-1};

int dy[9] = {0,0,0,1,-1,1,-1,1,-1};

char entrada[20][6];

int n;

int tabuleiro[MAXN][MAXN];

int valido(int x,int y){

return x >= 0 && x < MAXN && y >= 0 && y < MAXN && (tabuleiro[x][y] == LIVRE || tabuleiro[x][y] == PECA);

}

void addPeao(int x,int y){

int nx1 = x - 1, ny1 = y - 1;

int nx2 = x + 1, ny2 = y - 1;

if(nx1 >= 0 && nx1 < MAXN && ny1 >= 0 && ny1 < MAXN){

//printf("Loop1 %d %d\n",nx1,ny1);

if(tabuleiro[nx1][ny1] == LIVRE) tabuleiro[nx1][ny1] = ATACADA;

else if(tabuleiro[nx1][ny1] == PECA) tabuleiro[nx1][ny1] = SUPORTE; 

}

if(nx2 >= 0 && nx2 < MAXN && ny2 >= 0 && ny2 < MAXN){

//printf("Loop2 %d %d\n",nx2,ny2);

if(tabuleiro[nx2][ny2] == LIVRE) tabuleiro[nx2][ny2] = ATACADA;

else if(tabuleiro[nx2][ny2] == PECA) tabuleiro[nx2][ny2] = SUPORTE; 

}

}

void addBispo(int x,int y){

for(int i = x-1, j = y-1;i >= 0 && j >= 0;i--,j--){

if(tabuleiro[i][j] == LIVRE){

tabuleiro[i][j] = ATACADA;

}

else if(tabuleiro[i][j] == PECA){

tabuleiro[i][j] = SUPORTE;

break;

}

}

for(int i = x+1, j = y+1;i < MAXN && j < MAXN;i++,j++){

if(tabuleiro[i][j] == LIVRE){

tabuleiro[i][j] = ATACADA;

}

else if(tabuleiro[i][j] == PECA){

tabuleiro[i][j] = SUPORTE;

break;

}

}

for(int i = x-1, j = y+1;i >= 0 && j < MAXN;i--,j++){

if(tabuleiro[i][j] == LIVRE){

tabuleiro[i][j] = ATACADA;

}

else if(tabuleiro[i][j] == PECA){

tabuleiro[i][j] = SUPORTE;

break;

}

}

for(int i = x+1, j = y-1;i < MAXN && j >= 0;i++,j--){

if(tabuleiro[i][j] == LIVRE){

tabuleiro[i][j] = ATACADA;

}

else if(tabuleiro[i][j] == PECA){

tabuleiro[i][j] = SUPORTE;

break;

}

}

}

void addTorre(int x,int y){

for(int i=x-1;i>=0;i--){

//printf("Loop1 %d %d\n",i,y);

if(tabuleiro[i][y] == LIVRE){

tabuleiro[i][y] = ATACADA;

}

else if(tabuleiro[i][y] == PECA){

tabuleiro[i][y] = SUPORTE;

break;

}

}

for(int i=x+1;i<MAXN;i++){

///printf("Loop2 %d %d\n",i,y);

if(tabuleiro[i][y] == LIVRE){

tabuleiro[i][y] = ATACADA;

}

else if(tabuleiro[i][y] == PECA){

tabuleiro[i][y] = SUPORTE;

break;

}

}

for(int i=y-1;i>=0;i--){

//printf("Loop3 %d %d\n",x,i);

if(tabuleiro[x][i] == LIVRE){

tabuleiro[x][i] = ATACADA;

}

else if(tabuleiro[x][i] == PECA){

tabuleiro[x][i] = SUPORTE;

break;

}

}

for(int i=y+1;i<MAXN;i++){

//printf("Loop4 %d %d\n",x,i);

if(tabuleiro[x][i] == LIVRE){

tabuleiro[x][i] = ATACADA;

}

else if(tabuleiro[x][i] == PECA){

tabuleiro[x][i] = SUPORTE;

break;

}

}

}

void addRei(int x,int y){

for(int i=1;i<9;i++){

int nx = x + dx[i];

int ny = y + dy[i];

if(nx < 0 || ny < 0 || nx >= MAXN || ny >= MAXN) continue;

//printf("Loop %d: %d %d\n",i,nx,ny);

if(tabuleiro[nx][ny] == LIVRE) tabuleiro[nx][ny] = ATACADA;

else if(tabuleiro[nx][ny] == PECA) tabuleiro[nx][ny] = SUPORTE; 

}

}

int main(){

while(scanf("%d",&n) != EOF){

memset(tabuleiro,0,sizeof(tabuleiro));

for(int i=0;i<n;i++){

scanf("%s",entrada[i]);

tabuleiro[entrada[i][1] - 'a'][entrada[i][2] - '1'] = PECA;

}

//for(int ni=0;ni<MAXN;ni++){

// for(int nj=0;nj<MAXN;nj++){

// printf("%d ",tabuleiro[ni][nj]);

// }

// printf("\n");

//}

//printf("\n");

for(int i=0;i<n;i++){

if(entrada[i][0] == 'P') addPeao(entrada[i][1] - 'a',entrada[i][2] - '1');

if(entrada[i][0] == 'T' || entrada[i][0] == 'R') addTorre(entrada[i][1] - 'a',entrada[i][2] - '1');

if(entrada[i][0] == 'B' || entrada[i][0] == 'R') addBispo(entrada[i][1] - 'a',entrada[i][2] - '1');

if(entrada[i][0] == 'W') addRei(entrada[i][1] - 'a',entrada[i][2] - '1');

//for(int ni=0;ni<MAXN;ni++){

//for(int nj=0;nj<MAXN;nj++){

// printf("%d ",tabuleiro[ni][nj]);

//}

//printf("\n");

//}

//printf("\n");

}

scanf("%s",entrada[n]);

int xrei = entrada[n][1] - 'a', yrei = entrada[n][2] - '1';

int possivel = 0;

for(int i=0;i<9;i++){

if(valido(xrei + dx[i],yrei + dy[i])){

//printf("%d %d eh um escape\n",xrei + dx[i], yrei + dy[i]);

possivel = 1;

break;

}

} 

//for(int ni=0;ni<MAXN;ni++){

// for(int nj=0;nj<MAXN;nj++){

// printf("%d ",tabuleiro[ni][nj]);

// }

// printf("\n");

//}

//printf("\n");

if(possivel) printf("NAO\n");

else printf("SIM\n");

}

return 0;

}