Antiqueen
2021 TCO Parallel 1B · 2021-04-13 · by misof
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.
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.
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
1 1 1 Returns: 0
1 100 3 Returns: 0
100 1 7 Returns: 0
2 2 1 Returns: 0
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.
Submissions are judged against all 63 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Antiqueen with a public method int countPaths(int R, int C, int N) · 63 test cases · 2 s / 256 MB per case