HexGridPaths | Topcoder Archive

Problem Statement

Consider an infinite hexagonal grid numbered in a spiral (as shown in http://www.cut-the-knot.org/ctk/HexMosaic.gif , for example).

You are on the cell start. In each step, you can move from your current cell into one of the six adjacent ones. You must get to the cell finish using the smallest possible number of steps. Depending on the locations of your start and finish, there may be many possible paths. We will call them the good paths.

Some of the cells contain obstacles, such as mud, thorns, etc. The numbers of these cells are given as int[] obstacles. Going through these cells is unpleasant and you want to avoid all such cells.

Let P be the number of good paths that avoid all obstacles. Compute the value (P modulo 1,000,000,009).

Definition

Class:: HexGridPaths
Method:: pathCount
Parameters:: long, long, long[]
Returns:: int
Method signature:: int pathCount(long start, long finish, long[] obstacles)
(be sure your method is public)

Notes

The smallest possible number of steps in the definition of a good path is calculated for the empty grid, i.e., assuming that there are no obstacles. See example 3 for clarification.

Constraints

start will be between 1 and 10^12, inclusive.
finish will be between 1 and 10^12, inclusive.
start will not be equal to finish
obstacles will contain between 0 and 50 elements, inclusive.
Each element of obstacles will be between 1 and 10^12, inclusive.
No two elements of obstacles will be equal.
No element of obstacles will be equal to start.
No element of obstacles will be equal to finish.

Examples

```
1
```
```
61
```
```
{}
```
```
Returns: 1
```
There is a single good path: 1-7-19-37-61.
```
1
```
```
39
```
```
{32}
```
```
Returns: 6
```
There are six good paths from 1 to 39. The obstacle at 32 does not block any of these.
```
1
```
```
39
```
```
{8}
```
```
Returns: 2
```
This obstacle blocks four out of six good paths. The remaining two are 1-7-19-20-39 and 1-2-9-21-39.
```
24
```
```
16
```
```
{13,4,1,7}
```
```
Returns: 0
```
Each of the good paths is blocked by exactly one of the obstacles.
```
50
```
```
8
```
```
{6,12,22}
```
```
Returns: 11
```
```
55
```
```
44
```
```
{3,5,6}
```
```
Returns: 8
```

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.