DoNotTurn | Topcoder Archive

Problem Statement

There is a NxN maze where each cell contains either a wall or empty space. You are currently in the top-left cell at coordinates (0, 0) and your goal is to reach the bottom-right cell at coordinates (N-1, N-1) making as few turns as possible. You can choose any of the four cardinal directions as your starting direction. Then, from each cell, you can either move forward one cell in your current direction or turn left or right by 90 degrees. You can only walk into empty cells, not walls.
You are given ints M, X0, Y0, A, B, C and D. Generate lists X and Y, each of length M, using the following recursive definitions:
X[0] = X0 MOD P
X[i] = (X[i-1]*A+B) MOD P (note that X[i-1]*A+B may overflow a 32-bit integer)
Y[0] = Y0 MOD P
Y[i] = (Y[i-1]*C+D) MOD P (note that Y[i-1]*C+D may overflow a 32-bit integer)
Cell (x, y) of the maze contains a wall if and only if it is neither the top-left cell nor the bottom-right cell and there exists a value of i between 0 and M-1, inclusive, such that x=X[i] MOD N and y=Y[i] MOD N. Return the minimum number of turns you must make to reach the bottom-right cell of this maze, or return -1 if it is impossible.

Definition

Class:: DoNotTurn
Method:: minimumTurns
Parameters:: int, int, int, int, int, int, int, int, int
Returns:: int
Method signature:: int minimumTurns(int N, int X0, int A, int B, int Y0, int C, int D, int P, int M)
(be sure your method is public)

Notes

In the statement, "A MOD B" represents the remainder of integer division of A by B. For example, 14 MOD 5 = 4 and 20 MOD 4 = 0.
The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of allowed size within the given limits.

Constraints

N will be between 2 and 500, inclusive.
M will be between 0 and 1,000,000, inclusive.
X0, Y0, A, B, C and D will each be between 0 and 1,000,000, inclusive.
P will be between 1 and 1,000,000, inclusive.

Examples

```
2
```
```
0
```
```
0
```
```
1
```
```
0
```
```
0
```
```
1
```
```
10
```
```
2
```
```
Returns: 1
```
There are no walls, so you will have to make only one turn.
```
3
```
```
0
```
```
1
```
```
1
```
```
1
```
```
1
```
```
0
```
```
3
```
```
3
```
```
Returns: -1
```
The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell): .#. .#. .#. The target is unreachable.
```
3
```
```
0
```
```
1
```
```
1
```
```
1
```
```
1
```
```
1
```
```
3
```
```
3
```
```
Returns: 3
```
The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell): .#. ..# #.. There is only one possible path and it requires 3 turns.
```
10
```
```
911111
```
```
845499
```
```
866249
```
```
688029
```
```
742197
```
```
312197
```
```
384409
```
```
40
```
```
Returns: 12
```
The maze and the optimal path in it are given below ('#' denotes a wall, '.' denotes an empty cell, the path is illustrated using 'p' characters): pp##..#..# #pp..###.. .#p#.....# ##p...#.#. .#p.##.#.. ##p##.#... #pp####... pp#.#...#. p#pppp#... ppp##ppppp
```
5
```
```
23
```
```
2
```
```
3
```
```
35
```
```
5
```
```
7
```
```
9
```
```
3
```
```
Returns: 2
```
The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell): ...#. ..... ...#. ..... ..#..
```
2
```
```
0
```
```
0
```
```
0
```
```
0
```
```
0
```
```
0
```
```
1
```
```
0
```
```
Returns: 1
```

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.