Chess P44731

Statement

thehtml

Write a program that analyses several chess positions, very simplified. In particular, the black player only has his king, while the white player only has rooks, bishops and queens. Remember that kings can only do horizontal, vertical and diagonal movements, and just one step. The other pieces can move more than one square at a time: the rooks, horizontally and vertically; the bishops, diagonally; the queens, horizontally, vertically, and diagonally.

Your program must determine all the positions where the black king can move to, that is, all the neighbouring positions of the black king that are not threatened by any white piece. (If the king has an enemy piece around him and this one is not defended, the king can move to this position “killing” the enemy piece.) If the black king does not have any valid movement, print “checkmate” if the position of the king is threatened, and “stalemate” if it is not.

Input

Input starts with the number of test boards n, followed by n boards. Each board consists of the position of the black king, followed by the number of white pieces m (between 0 and 63), followed by m pieces, each one of them defined by its type (R, B or Q) and its position. The positions are defined by a column (a letter between a and h) and a row (a number between 1 and 8). All the pieces of a board are in different positions.

Output

For each board, print its number starting at 1, followed by all the positions where the black king can move to, in alphabetical order. If there is no possible movement, print “checkmate” or “stalemate” depending on the case.

Scoring

• Test1:  ‍20 Points ‍

Solving cases like those in sample 1, where the white player only has rooks.

• Test2:  ‍20 Points ‍

Solving cases like those in sample 2, where the white player only has bishops.

• Test3:  ‍20 Points ‍

Solving cases like those in sample 3, where the white player only has queens.

• Test4:  ‍40 Points ‍

Solving cases like those in sample 4, where the white player has pieces of the three kinds.

Public test cases
• Input

```7
e8 0
a4 1 Rb8
h3 2 Rh1 Rg5
h3 2 Rh1 Rg4
a1 2 Rb8 Rh2
c4 4 Rb4 Rc3 Rc5 Rd4
f6 4 Rg7 Ra7 Re2 Rh5
```

Output

```1: d7 d8 e7 f7 f8
2: a3 a5
3: checkmate
4: g4
5: stalemate
6: checkmate
7: stalemate
```
• Input

```6
a4 1 Bf8
h3 4 Bf1 Bg3 Be6 Bb8
h3 3 Bf1 Bg3 Be6
a1 3 Bg8 Bg6 Ba3
c4 4 Ba5 Bf1 Bf2 Bf7
f6 4 Bd6 Be6 Bf5 Bh6
```

Output

```1: a5 b3 b5
2: checkmate
3: g3
4: stalemate
5: checkmate
6: stalemate
```
• Input

```6
a4 1 Qb6
h3 2 Qg1 Qg4
h3 2 Qh1 Qg4
a1 1 Qc2
c4 2 Qb3 Qd5
f6 2 Qe8 Qg4
```

Output

```1: a3
2: checkmate
3: g4
4: stalemate
5: checkmate
6: stalemate
```
• Input

```16
e5 2 Bd6 Rf6
e5 2 Bd4 Rf6
e5 2 Qf2 Rf6
e5 2 Qe4 Rf6
e5 2 Qf4 Bf6
e5 2 Qf3 Bf5
e5 3 Qg4 Rf5 Bb4
e5 2 Bf5 Rg5
h8 2 Rg1 Bg8
h8 2 Rg7 Ba1
e2 3 Ba8 Qc1 Rf3
a2 3 Bb2 Bc2 Rb8
a1 3 Ra8 Qh8 Bh7
d5 3 Rc6 Qf4 Bf3
d5 7 Bc5 Bd6 Bd4 Be5 Qf1 Bg2 Rf6
h1 4 Bf2 Bg1 Bg2 Rh2
```

Output

```1: d4 d5 e4 f6
2: d4 d5 e4
3: d5 e4
4: e4 f6
5: d5 e6 f4
6: d4 d6 f6
7: e6
8: d4 d5 d6 f4 f6
9: stalemate
10: stalemate
11: stalemate
12: stalemate
13: checkmate
14: checkmate
15: checkmate
16: checkmate
```
• Information
Author