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
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.
200
200
200
Returns: 474304285
100
100
100
Returns: 135157940
70
35
47
Returns: 308486456
193
197
198
Returns: 276470345
7
8
2
Returns: 64904
91
17
111
Returns: 495152349
142
117
147
Returns: 305907689
88
66
132
Returns: 35985967
99
101
158
Returns: 567306063
11
108
169
Returns: 222225345
7
27
1
Returns: 27440
68
124
186
Returns: 817178478
140
3
81
Returns: 773745457
146
110
59
Returns: 106656689
61
134
132
Returns: 366943303
92
114
62
Returns: 181944167
9
144
96
Returns: 575020195
184
177
91
Returns: 393900295
154
88
143
Returns: 665377253
148
196
51
Returns: 317084596
62
187
10
Returns: 178807001
33
86
26
Returns: 722790496
93
149
99
Returns: 471648414
131
139
65
Returns: 864250456
25
167
59
Returns: 28495774
179
86
56
Returns: 496567963
121
191
29
Returns: 99928751
198
107
155
Returns: 347874115
91
173
74
Returns: 515813438
198
62
143
Returns: 284231076
67
92
137
Returns: 661175955
145
11
124
Returns: 158965303
80
145
200
Returns: 573750513
102
67
187
Returns: 177621054
133
57
156
Returns: 374555843
183
200
186
Returns: 602148169
192
195
188
Returns: 972789095
199
197
184
Returns: 876932166
194
180
185
Returns: 195678071
197
200
182
Returns: 661076100
182
188
196
Returns: 424135084
199
197
195
Returns: 303155159
193
191
181
Returns: 554223880
199
188
200
Returns: 839778660
199
196
195
Returns: 415225756
200
190
180
Returns: 233815198
198
187
186
Returns: 167727141
191
193
185
Returns: 48559974
185
195
186
Returns: 61171841
184
183
184
Returns: 751188183
198
191
196
Returns: 205758795
192
183
188
Returns: 339030330
194
180
200
Returns: 350005108
183
193
182
Returns: 500990247
191
180
188
Returns: 906129203
100
200
100
Returns: 491514037