Hide

Problem J
General Knight

For the uninitiated, chess is a board game is played on a grid of $8 \times 8$ squares. The rows are numbered $1$ to $8$ with row $1$ at the bottom and columns are labeled with lowercase $a$ to $h$. The label of a square is its column, then its row. For example, valid square labels are $a1$ and $e5$.

In chess, a piece threatens a square on the board if the piece can move to that square in one move. The knight is one of the more fearsome chess pieces, as it moves differently from the other pieces. In a single move, a knight can move two rows and one column or one column and two rows. The image below shows the squares a standard chess knight threatens if it starts in square $e5$.

\includegraphics[width=0.75\textwidth ]{knight_e5}

The standard chess knight is a $(2, 1)$-knight. The more general version is an $(a, b)$-knight, which in one move can move either $a$ rows and $b$ columns, or $b$ rows and $a$ columns. Citizens of the chessboard are concerned, as they don’t know how powerful these new knights are. Given an $(a, b)$-knight and its starting square, which squares does it threaten?

Input

Input consists of two lines. The first line has two space-separated integers $a$ and $b$, the properties of the knight. It is guaranteed that $0 \leq a, b < 8$ and $\max (a, b) > 0$. The second line contains the starting location of the $(a, b)$-knight. This is given in standard chess notation as described above.

Output

First, output an integer $k$, the number of squares the knight can reach. On the second line, output $k$ space separated strings, the positions the knight can move to in exactly one move. Sort these positions in increasing column order, breaking ties by increasing row.

Sample Input 1 Sample Output 1
4 5
a1
2
e6 f5
Sample Input 2 Sample Output 2
2 1
e5
8
c4 c6 d3 d7 f3 f7 g4 g6
CPU Time limit 1 second
Memory limit 1024 MB
Authors
Ethan Arnold and Arnav Sastry
Source 2019 UT Invitational Programming Contest
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in