Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1206
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1206
Challenge of St. Petersburg
By Marcio T. I. Oshiro 
Brazil
Timelimit: 1
The Russia has always been the cradle of great chess masters. Few people know that the FIDE (World Chess Federation), which is the highest body regulating the game of chess was founded in 1924 from a movement begun 10 years before in the world championship of the sport that took place in St. Petersburg in 1914. Today, the top 10 players in the world, according to FIDE, three are Russians.
The tournament of St. Petersburg was also known by the attempts of the great masters of popularizing the game. At the time the greatest masters (like Capablanca) took to the streets to propose challenges for people in order to interest them to practice the game. One of these challenges was known as the Challenge of St. Petersburg. The great master rode a situation where the white pieces had only the king, and the goal was the person who said if the white king was or not in checkmate.
In the situation described above, the white king is checkmated if he is being attacked, and every move he makes leads him to a square that is also being attacked.
What you need to know about chess
Consider that initially the black chess pieces are at lines 7 and 8 while the white chess pieces starts at lines 1 and 2. There aren’t two chess pieces in the same square. The chess pieces considered in the problem (pawn, rook, bishop, queen and king) can’t go over to other parts, in other words, if during chess pieces’ movement there is any other chess piece on its way you must stop before or attacking the chess piece (if it is the opponent), taking its place. The movement and the attack of each type of chess peace are as follows:
# Pawn: walking just one square forward (toward the line 1) can attack in any of the two diagonals immediately in front;
# Rook: walk / attacks how many squares you want horizontally or vertically;
# Bishop: walking / attacking how many squares you want diagonally;
# Queen: walk / attacks how many squares you want horizontally or vertically, or diagonally;
# King: walk / attacks just a square or horizontally, or vertically, or diagonally.
Input
The input consists of several test cases and ends with the end of file (EOF). The first line of each test case contains one integer N (2 ≤ N ≤ 10) indicating the number of black chess pieces. The next line contains the description of the positions of N black chess peaces separated by a space. The third line contains the description of the white king.
A description of one chess piece consists of 3 characters. The first indicates whether the chess piece is a pawn (P)(Peão), rook(T)(Torre), Bishop (B)(Bispo), Queen(R)(Rainha) or King (W)(Rei). Note that the great master did not use horses to facilitate who was still just learning the game. The second character between 'a' and 'h', indicates the column in which the chess peace is and the third, from '1 'to '8' indicates the line.
Neither of the test cases is the situation in which the white king and the black king are adjacent.
Output
For each test case, print a line with the word SIM (YES) if the white king is in checkmate, or the word NAO (NO), otherwise.
| Sample Input | Sample Output |
|
4 |
NAO |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#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;
}
Input
Tc3 Te4 Bf4 Wa8
Wd1
5
Wb5 Pf3 Rh7 Te1 Tg1
Wh1
4
Wa8 Ta1 Ta3 Rd2
We2
Output
SIM
NAO