Chess World: Minimum Moves and Distinct Paths

In Chess World there is an R×C board with R rows and C columns (with R ≥ C). The rows are numbered 1 through R and columns 1 through C. There are five kinds of pieces: Pawn, Rook, Bishop, Queen, and King. (Note that the Knight is missing in Chess World.)

Each type of piece can move as follows in one move:

• Pawn: Can only move one cell downwards (from row r to row r+1) without changing its column.
• Rook: Can move any number of cells horizontally or vertically.
• Bishop: Can move any number of cells diagonally (i.e. along directions where \(\vert \Delta r\vert = \vert \Delta c\vert\)).
• Queen: Combines the moves of the Rook and Bishop.
• King: Can move one step in any of the eight adjacent cells.

Recently, some pieces mysteriously disappeared. The remaining pieces now all wish to move from their starting cell to their destination in as few moves as possible. Moreover, they want to know the number of distinct shortest paths. Two paths are considered different if there is at least one cell that is visited in one path and not in the other.

You are given the type of a piece as well as its starting and destination column indices. The piece starts at cell \((1, c_1)\) and must reach \((R, c_R)\). For the given piece type and values of \(c_1\) and \(c_R\), determine the minimum number of moves required and the number of distinct shortest paths. If it is impossible for the piece to reach the destination, output -1 0.

Movement details in mathematical terms:

• Pawn: Moves from \((r, c)\) to \((r+1, c)\). Thus, a solution exists only if \(c_1 = c_R\); the minimum moves is \(R-1\) and there is only 1 path.
• Rook: Moves vertically or horizontally. It can reach \((R, c_R)\) in 1 move if \(c_1 = c_R\) (vertical move), and in 2 moves if \(c_1 \neq c_R\) (using horizontal and vertical moves, which give 2 distinct intermediate choices).
• Bishop: Moves diagonally (i.e. a move from \((r,c)\) to some \((r', c')\) is legal if \(|r'-r| = |c'-c|\)). A necessary condition for the Bishop to reach the destination is that the starting and ending cells are of the same color, i.e. \((1+c_1)\equiv (R+c_R)\pmod{2}\). Moreover, if \(|R-1| = |c_R-c_1|\) then the Bishop can do it in 1 move; otherwise, it can always do it in 2 moves. In the 2‐move case, the number of distinct paths equals the number of valid intermediate cells \(X=(r,c)\) (with \(1 \le r \le R, 1 \le c \le C\) and \(X \neq (1,c_1)\) and \(X \neq (R,c_R)\)) such that both moves \((1,c_1)\to X\) and \(X\to(R,c_R)\) are legal bishop moves. In our solution we compute up to 2 candidate intermediate cells (using the equations \[ \begin{aligned} (r-c) &= 1-c_1,\quad r+c &= R+c_R,\\ (r-c) &= R-c_R,\quad r+c &= 1+c_1. \end{aligned} \] and count those that lie within the board).
• Queen: Combines the moves of the Rook and Bishop. Thus, the Queen can reach the destination in 1 move if either \(c_1 = c_R\) (vertical move) or \(|R-1| = |c_R-c_1|\) (diagonal move). Otherwise, the minimum moves is 2, and the number of distinct paths is the number of cells \(X\) (with \(1 \le r \le R, 1 \le c \le C\) and \(X \neq (1,c_1)\) and \(X \neq (R,c_R)\)) such that both moves \((1,c_1)\to X\) and \(X\to(R,c_R)\) are legal Queen moves. We enumerate such candidates by considering intersections of the following four lines from the start:
  • Row: \(r=1\), Column: \(c=c_1\), Diagonal: \(r-c=1-c_1\), Anti-diagonal: \(r+c=1+c_1\), and similarly for the destination cell \((R,c_R)\): Row \(r=R\), Column \(c=c_R\), Diagonal \(r-c=R-c_R\) and Anti-diagonal \(r+c=R+c_R\).
• King: Moves one step in any direction. The shortest path length is \(m=\max(R-1, |c_R-c_1|)\). In the case \(R-1 \ge |c_R-c_1|\), one must take exactly \(|c_R-c_1|\) diagonal moves (which change both row and column) and the remaining \((R-1-|c_R-c_1|)\) vertical moves. Hence, the number of distinct paths equals \(\binom{R-1}{|c_R-c_1|}\). If \(|c_R-c_1| > R-1\), then in the minimal \(|c_R-c_1|\) moves, exactly \(R-1\) moves must be diagonal and the rest horizontal, so the number of paths is \(\binom{|c_R-c_1|}{R-1}\).

Input and output format: See below.

inputFormat

The input consists of a single test case in the following format:

R C
piece_type
c1 cR

Here, R and C (integers) denote the number of rows and columns respectively (with R ≥ C). The string piece_type is one of Pawn, Rook, Bishop, Queen, or King. Finally, c1 and cR (integers) denote the starting column (in row 1) and destination column (in row R) respectively.

outputFormat

Output two space‐separated integers. The first is the minimum number of moves required for the piece to move from \((1, c_1)\) to \((R, c_R)\), and the second is the number of distinct shortest paths. If it is impossible to reach the destination, output -1 0 instead.

sample

8 8
Rook
3 6

2 2