DoNotTurn

SRM 436 · 2009-03-11 · by Gluk

SRM 436 · 2009-03-11 · by Gluk · Graph Theory

Show categories

Class Name: DoNotTurn

Return Type: int

Method Name: minimumTurns

Arg Types: (int, int, int, int, int, int, int, int, int)

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.

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
1
2
3
5
7
1
997
30
Returns: -1

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

66)

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): ...#. ..... ...#. ..... ..#..

Submissions are judged against all 119 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DoNotTurn with a public method int minimumTurns(int N, int X0, int A, int B, int Y0, int C, int D, int P, int M) · 119 test cases · 2 s / 256 MB per case