Statistics

Problem Statement for "DoNotTurn"

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

  1. 2

    0

    0

    1

    0

    0

    1

    10

    2

    Returns: 1

    There are no walls, so you will have to make only one turn.

  2. 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. 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.

  4. 10

    1

    2

    3

    5

    7

    1

    997

    30

    Returns: -1

  5. 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

  6. 15

    185917

    104311

    3527

    27409

    127541

    46723

    53299

    16

    Returns: 2

  7. 101

    887

    1913

    132661

    193057

    208991

    221261

    223423

    6161

    Returns: -1

  8. 57

    122701

    16069

    223637

    295769

    303691

    188443

    103561

    1179

    Returns: -1

  9. 13

    354451

    196181

    44893

    165587

    78583

    328051

    69163

    137

    Returns: -1

  10. 57

    385943

    225221

    138209

    90071

    101737

    319069

    5927

    2092

    Returns: -1

  11. 26

    15797

    1879

    351691

    93629

    92593

    215723

    257671

    23

    Returns: 2

  12. 56

    67547

    279137

    168193

    163901

    364499

    279511

    33107

    2524

    Returns: -1

  13. 39

    224201

    209441

    126229

    48259

    74821

    150989

    303817

    947

    Returns: -1

  14. 54

    120277

    54421

    243889

    177433

    18181

    261229

    182549

    1280

    Returns: -1

  15. 133

    346043

    258353

    103991

    151517

    20411

    372061

    254329

    1017

    Returns: 7

  16. 121

    213289

    62467

    57529

    309667

    170851

    49633

    182179

    10907

    Returns: -1

  17. 286

    208009

    253937

    284159

    270163

    170857

    38197

    128749

    11860

    Returns: 30

  18. 250

    246173

    151391

    31981

    364571

    352711

    200293

    120431

    4687

    Returns: 12

  19. 157

    109201

    163169

    92243

    378919

    101921

    277231

    207481

    3537

    Returns: 14

  20. 122

    140269

    181001

    339769

    7001

    383839

    209519

    14033

    14080

    Returns: -1

  21. 110

    231271

    244033

    64879

    319831

    38299

    33623

    278879

    4343

    Returns: 43

  22. 191

    116731

    44171

    274831

    316891

    264643

    220687

    280627

    30498

    Returns: -1

  23. 181

    17389

    305111

    324223

    69497

    35591

    201809

    3323

    12023

    Returns: 13

  24. 228

    255511

    197837

    21577

    155453

    66361

    259691

    99109

    46421

    Returns: -1

  25. 500

    193451

    232007

    51329

    182279

    370471

    259531

    354139

    94231

    Returns: 223

  26. 500

    384079

    163697

    385261

    29411

    230551

    28433

    155783

    6830

    Returns: 7

  27. 500

    98993

    75617

    289721

    145463

    66373

    231779

    222199

    206841

    Returns: -1

  28. 398

    234613

    325021

    314491

    230383

    269713

    206909

    131611

    22255

    Returns: 40

  29. 438

    346039

    81343

    61553

    222461

    260677

    214363

    122389

    97491

    Returns: -1

  30. 402

    225427

    228797

    257639

    304481

    47389

    210811

    330331

    102456

    Returns: -1

  31. 469

    11821

    248063

    376099

    108533

    208213

    104971

    56179

    83973

    Returns: 24

  32. 357

    279443

    49409

    113089

    23327

    22447

    237271

    310867

    60665

    Returns: -1

  33. 500

    102217

    167017

    181141

    48647

    111623

    276763

    108127

    150300

    Returns: 85

  34. 500

    271393

    102679

    362347

    39667

    18947

    296437

    190313

    132261

    Returns: -1

  35. 476

    333667

    242453

    111253

    32027

    182627

    75541

    99089

    110345

    Returns: -1

  36. 345

    35227

    177787

    133109

    179381

    299993

    184279

    134363

    7141

    Returns: 13

  37. 449

    139333

    1181

    264601

    30553

    229763

    328481

    177269

    88099

    Returns: 155

  38. 488

    296563

    201673

    124633

    367163

    232937

    57073

    131251

    137636

    Returns: -1

  39. 413

    225373

    7127

    114217

    15731

    236527

    41213

    321833

    30275

    Returns: 48

  40. 421

    324757

    3449

    39371

    264619

    227501

    72031

    19031

    215187

    Returns: 32

  41. 500

    110233

    128659

    245383

    303619

    305401

    191099

    225077

    196700

    Returns: -1

  42. 454

    232669

    142031

    85427

    42793

    325189

    19087

    151909

    78263

    Returns: -1

  43. 500

    74941

    107069

    33857

    305839

    42223

    96763

    297719

    712025

    Returns: -1

  44. 500

    226697

    126143

    325769

    76039

    328637

    76423

    83843

    762439

    Returns: 177

  45. 500

    24001

    190339

    151579

    28537

    87337

    340393

    77617

    1000000

    Returns: 144

  46. 500

    23603

    12967

    16649

    116789

    349939

    140617

    153929

    1000000

    Returns: 28

  47. 500

    319819

    258607

    140281

    87509

    823

    190717

    366841

    116000

    Returns: -1

  48. 500

    85991

    254753

    362951

    154981

    339811

    1487

    361159

    150000

    Returns: -1

  49. 500

    44927

    73819

    134677

    811

    148249

    24229

    244873

    60000

    Returns: 106

  50. 500

    245759

    257797

    303727

    192547

    255259

    45061

    256939

    125000

    Returns: -1

  51. 500

    330731

    238727

    264029

    25409

    201359

    363959

    16657

    84000

    Returns: 21

  52. 500

    228619

    99823

    353161

    128657

    258977

    72421

    49757

    626871

    Returns: 82

  53. 500

    32503

    344963

    157411

    23603

    295153

    55457

    375247

    41465

    Returns: 65

  54. 500

    163367

    683

    281923

    35069

    142969

    106963

    383041

    520000

    Returns: 3

  55. 500

    83101

    48947

    228773

    337691

    360197

    63977

    294181

    241616

    Returns: -1

  56. 500

    162901

    352637

    246641

    47947

    235231

    208319

    149771

    520000

    Returns: -1

  57. 500

    195053

    86029

    139987

    122027

    9739

    300743

    64319

    577530

    Returns: 46

  58. 500

    20627

    64811

    49747

    238673

    162527

    222311

    260191

    380000

    Returns: -1

  59. 500

    317351

    217463

    65519

    364621

    333787

    137941

    380819

    197222

    Returns: -1

  60. 500

    157543

    231463

    264839

    13757

    97283

    87803

    144223

    165337

    Returns: 116

  61. 500

    342233

    138617

    140191

    345571

    106109

    136531

    208697

    135500

    Returns: -1

  62. 500

    276079

    277309

    43867

    65677

    92467

    253307

    348457

    96000

    Returns: -1

  63. 500

    346961

    66763

    187633

    242819

    156139

    256093

    27031

    873697

    Returns: 38

  64. 500

    123821

    105527

    260179

    45007

    139199

    19603

    251263

    1000000

    Returns: -1

  65. 500

    1

    1

    11

    19

    23

    13

    123612

    1000000

    Returns: -1

  66. 500

    0

    0

    0

    0

    0

    0

    1

    0

    Returns: 1

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

  68. 5

    285579

    517262

    509057

    883467

    642170

    174328

    280287

    8

    Returns: 4

  69. 5

    787680

    382519

    350992

    365719

    147717

    750884

    151621

    14

    Returns: 6

  70. 5

    232451

    547944

    933741

    47049

    27632

    460172

    903287

    16

    Returns: 7

  71. 10

    476668

    212942

    438004

    782469

    551887

    949313

    499293

    42

    Returns: 19

  72. 10

    843057

    978778

    542689

    64282

    137049

    355839

    177071

    36

    Returns: 16

  73. 10

    231514

    235685

    852059

    757288

    620325

    573583

    445011

    40

    Returns: 14

  74. 50

    43755

    592

    29007

    863409

    249818

    941221

    387713

    1201

    Returns: 59

  75. 50

    355802

    355896

    974079

    179217

    335344

    153140

    177169

    1088

    Returns: 64

  76. 50

    407538

    821981

    536292

    94640

    466121

    184998

    207987

    1106

    Returns: 45

  77. 500

    793524

    420491

    500689

    502370

    760667

    765752

    288009

    141686

    Returns: 309

  78. 500

    150641

    938433

    893954

    740218

    379339

    636398

    133863

    112737

    Returns: 310

  79. 500

    401432

    272036

    57307

    344730

    894126

    652129

    247685

    177855

    Returns: 390

  80. 500

    762761

    530466

    423248

    234589

    714941

    18436

    965995

    243196

    Returns: 494

  81. 2

    0

    0

    0

    0

    0

    0

    1

    0

    Returns: 1

  82. 50

    17

    2

    3

    4

    5

    677

    7777

    77

    Returns: 1

  83. 500

    911111

    845499

    866249

    688029

    742197

    312197

    384409

    51935

    Returns: 82

  84. 500

    911111

    845499

    866249

    688029

    742197

    312197

    384409

    40000

    Returns: 59

  85. 500

    911111

    845499

    866249

    688029

    742197

    312197

    384409

    40

    Returns: 1

  86. 500

    911111

    845499

    866249

    688029

    742197

    312197

    384409

    51500

    Returns: 82

  87. 500

    44162

    93615

    582302

    696024

    544404

    188109

    878703

    258895

    Returns: 426

  88. 500

    800000

    999999

    999998

    999997

    999996

    899991

    999999

    1000000

    Returns: 2

  89. 500

    911111

    845499

    866249

    688029

    742197

    312197

    384409

    51200

    Returns: 82

  90. 500

    1

    1

    1

    1

    1

    1

    1

    1000000

    Returns: 1

  91. 300

    100

    100

    100

    202

    202

    202

    33333

    100000

    Returns: 1

  92. 500

    1991

    1992

    1993

    1994

    1995

    1996

    1000000

    1000000

    Returns: 1

  93. 500

    1000

    1000000

    1000000

    1024

    999999

    999999

    4096

    5000

    Returns: 2

  94. 500

    911111

    845499

    866249

    688029

    742197

    312197

    384409

    50000

    Returns: 76

  95. 500

    1000000

    324345

    234324

    234444

    786873

    924876

    1000000

    1000000

    Returns: 2

  96. 500

    1000000

    1000000

    1000000

    1000000

    1000000

    1000000

    999991

    1000000

    Returns: 1

  97. 500

    911111

    845499

    866249

    688029

    742197

    312197

    384409

    10000

    Returns: 11

  98. 2

    0

    0

    0

    0

    0

    0

    1

    1000000

    Returns: 1

  99. 500

    5

    6

    7

    8

    9

    9

    6

    10000

    Returns: 1

  100. 500

    1000

    1

    20

    1500

    1

    30

    1000000

    1000000

    Returns: 1

  101. 500

    911111

    845499

    866249

    688029

    742197

    312197

    384409

    4000

    Returns: 4

  102. 500

    1

    123

    343243

    123

    2343

    3243

    23434

    1000000

    Returns: 14

  103. 500

    1000000

    999999

    1000000

    999997

    999857

    365789

    100009

    999995

    Returns: 2

  104. 3

    2

    1

    1

    2

    1

    1

    7

    0

    Returns: 1

  105. 500

    123123

    3231

    123453

    132412

    1234

    1234

    124324

    20000

    Returns: 1

  106. 500

    132456

    123

    12345

    12347

    1231

    321324

    10000

    1000000

    Returns: 1

  107. 500

    999999

    1000000

    1000000

    1000000

    1000000

    1000000

    1000000

    1000000

    Returns: 1

  108. 5

    4

    1

    5

    4

    1

    5

    1000000

    10

    Returns: 1

  109. 2

    2

    0

    3

    2

    0

    3

    10

    2

    Returns: 1

  110. 499

    921671

    923979

    921273

    953671

    923577

    925972

    953679

    923699

    Returns: -1

  111. 500

    0

    500001

    600001

    0

    700001

    800001

    999997

    100000

    Returns: 3

  112. 7

    15156

    19102

    28002

    23920

    21595

    18189

    30678

    9

    Returns: 1

  113. 2

    0

    0

    1

    1

    0

    1

    2

    2

    Returns: 1

  114. 3

    5

    0

    0

    5

    0

    0

    6

    1

    Returns: 1

  115. 500

    911111

    800496

    800496

    688029

    742197

    312197

    799997

    40

    Returns: 1

  116. 2

    1

    1

    1

    0

    1

    1

    100

    1

    Returns: 1

  117. 7

    21077

    3034

    18443

    651

    22863

    10607

    27898

    5

    Returns: 1

  118. 500

    498

    1

    1

    499

    2

    0

    12345

    2

    Returns: -1

  119. 2

    1

    1

    1

    1

    1

    1

    30

    20

    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.
This problem was used for: