Chess P44731


Statement
 

pdf   zip

html

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
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++