Antiqueen | Topcoder Archive

Problem Statement

An antiqueen is a chess piece that is the opposite of a chess queen - that is, it can move from one cell to another if and only if that move is not a valid queen move. Note that the antiqueen does have to move: staying on the current square is not a valid antiqueen move.

You have a rectangular board with R rows and C columns. You have to start by placing the antiqueen onto any square of the board. Then you have to make a sequence of N valid moves with the antiqueen (always continuing from the square where the previous move ended).

In how many different ways can the above sequence of actions be performed? Two ways are different if the antiqueen visits a different sequence of N+1 squares. Return the number of ways modulo 10^9 + 7.

Definition

Class:: Antiqueen
Method:: countPaths
Parameters:: int, int, int
Returns:: int
Method signature:: int countPaths(int R, int C, int N)
(be sure your method is public)

Notes

A chess queen can move from one cell to another if and only if the cells lie in the same row, in the same column, or on the same diagonal. This includes all shorter diagonals in both directions.

Constraints

R will be between 1 and 200, inclusive.
C will be between 1 and 200, inclusive.
N will be between 1 and 200, inclusive.

Examples

```
3
```
```
3
```
```
1
```
```
Returns: 16
```
You have a 3x3 board. You are asked to place the antiqueen somewhere and then to make one valid move. You cannot start in the center as then you won't have a valid move. If you start anywhere else, you will have two valid moves to choose from. Three of the 16 valid solutions are shown below: 0 is where the antiqueen starts and 1 is where it jumps. ..0 0.. ... ... ..1 0.. .1. ... ..1
```
2
```
```
3
```
```
100
```
```
Returns: 4
```
You must hop back and forth between two opposite corners of this rectangle. Thus, there are four possible sequences of actions (one starting in each corner).
```
2
```
```
4
```
```
100
```
```
Returns: 9613417
```
Here the antiqueen has a bit more freedom. The exact number of ways in which you can perform 100 consecutive moves on this board is 6002082144827584333108. Remember that the correct return value is this number modulo 10^9 + 7.
```
7
```
```
8
```
```
2
```
```
Returns: 64904
```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.