Statistics

Problem Statement for "DrivingAround"

Problem Statement

You are picking up your friend from the airport, and you just got a call - your friend's flight was delayed! You know exactly how long it will be in minutes before your friend will be ready to get picked up, and you want to drive around until that point in time, arriving at the airport at exactly that time. You want to find out how many ways there are to reach the airport in exactly that amount of time.

The city layout is given as a String[] adj. The ith character of the jth element of adj is '.' if there is no road connecting intersection i to intersection j (both zero-indexed). If there is a road from intersection i to intersection j, the number of minutes it takes to travel that road is given as a number from '1' to '5'. Roads are not necessarily two-way, and two-way roads may not be the same speed both ways. You are at intersection start when you get your friend's call, and the airport is at intersection finish. Calculate the number of ways to get from intersection start to intersection finish in exactly time minutes. Since this number might be rather large, return the answer modulo 1000003.

Definition

Class:
DrivingAround
Method:
numberOfWays
Parameters:
String[], int, int, int
Returns:
int
Method signature:
int numberOfWays(String[] adj, int start, int finish, int time)
(be sure your method is public)

Constraints

  • adj will contain between 1 and 10 elements, inclusive.
  • The number of characters in each element of adj will be the same as the number of elements in adj.
  • Each character in adj will be a '.' or a digit between '1' and '5', inclusive.
  • start and finish will each be between 0 and n-1, inclusive, where n is the number of elements in adj.
  • The ith character of the ith element of adj will be '.', for all i.
  • time will be between 1 and 1000000000, inclusive.

Examples

  1. {".12", "2.1", "12."}

    0

    2

    5

    Returns: 8

    There are 8 ways: 0->1->2->0->1->2 0->1->2->0->2 0->1->2->1->2 0->1->0->1->2 0->1->0->2 0->2->0->1->2 0->2->1->2 0->2->0->2

  2. {"....52....", "..5.......", "..........", ".......1..", "......42.2", "5...4.....", ".5...4...1", "......5...", ".3244.....", ".........."}

    2

    2

    10

    Returns: 0

  3. {"...14....1", "......13..", ".2...4....", "....52.5..", "1.3..4....", ".3....35.5", "4......1.1", "..4.4.1.54", "....4.11.5", "31144.2.4."}

    7

    2

    100

    Returns: 316984

  4. {"...43..4.4", "......1.3.", ".5......4.", "34.......2", "..........", "........1.", "35.......4", "....2.2..4", "5...5..5..", "1....2..4."}

    5

    5

    10000

    Returns: 28404

  5. {".....3.25.", "..3...3533", ".5.421.22.", "42....3121", "5421.1.114", "1.5.1.513.", "..513..5.1", "2.14142..4", "5.334333.1", "1....5.44."}

    6

    4

    10000000

    Returns: 863687

  6. {".231442123", "..41121512", "41.2..5511", "213.515224", "4135.1213.", "41354.4.22", "211231.4.1", "4445545.52", "5.4254.4.1", "321344441."}

    1

    3

    100000000

    Returns: 851713

  7. {".121515213", "3.23114121", "21.2222151", "433.5.4221", "1422..5453", "53152.1433", "55414..234", "4444315.43", ".333..35.2", "555152134."}

    8

    7

    1000000000

    Returns: 883368

  8. {"..134.", "..453.", ".4..33", "3....3", "2444.4", "453..."}

    0

    4

    10

    Returns: 7

  9. {".224", "5.3.", "12.1", "153."}

    3

    1

    10

    Returns: 14

  10. {".121515213", "3.23114121", "21.2222151", "433.5.4221", "1422..5453", "53152.1433", "55414..234", "4444315.43", ".333..35.2", "555152134."}

    8

    7

    536870911

    Returns: 935149

  11. {".5", ".."}

    1

    0

    10

    Returns: 0

  12. {"...", "...", "..."}

    2

    1

    10

    Returns: 0

  13. {"....", "....", "...4", "..3."}

    2

    0

    10

    Returns: 0

  14. {".....", "1....", "2....", ".....", "....."}

    2

    1

    10

    Returns: 0

  15. {".241.1", "...5..", ".1.12.", "223.2.", "4.45..", "....3."}

    5

    1

    10

    Returns: 3

  16. {"..1143.", "4.43544", ".2.152.", "442..25", "3.11.51", "2112..4", ".4114.."}

    6

    4

    10

    Returns: 8

  17. {".2..31..", "..33....", "...21...", "..3..3..", ".2.3.31.", "2..1....", "11...5.3", "2.5...1."}

    1

    0

    10

    Returns: 3

  18. {".3...35..", "......25.", "25.......", "..2...14.", ".....4..4", "..3.3.4.4", "........3", "..5..53..", "54.....2."}

    1

    8

    10

    Returns: 0

  19. {".......3..", "..........", ".5........", "..........", "..........", "..........", "..........", ".........3", "..........", ".........."}

    3

    5

    100

    Returns: 0

  20. {".112.44434", "4..44..433", "44.31.414.", "23..324441", "4444.341.2", "4.444.1442", "444243.143", "13..121.1.", "33421444.2", "4.242414.."}

    0

    6

    1000

    Returns: 152773

  21. {"..........", ".....2.4..", ".4........", ".......2..", "2.5.......", "........4.", "..........", ".....21...", ".......1..", ".........."}

    8

    2

    10000

    Returns: 0

  22. {".23.514553", "4.14.55.31", ".3.1.45154", "1.5.214..4", ".544.45433", "54354.4142", "442.21.424", "1444244.14", "531341.4.2", "14..3.445."}

    9

    0

    100000

    Returns: 856057

  23. {"..........", "...5.1..1.", "......2..2", "..........", "..........", "..........", "..........", "..........", "..........", "..2......."}

    8

    9

    1000000

    Returns: 0

  24. {"..........", "..........", "..........", ".3.......5", "..........", ".......4.2", "..........", "..........", "..........", ".........."}

    0

    4

    10000000

    Returns: 0

  25. {".212242515", "..5.2514.3", "21.2..55.5", "155.5434.2", "1545.25...", "322.3.4345", "54441..514", "521.2.2.11", "...52545..", "12..55115."}

    2

    6

    100000000

    Returns: 724103

  26. {".2.2333113", "3.212344.4", "31.3513.24", "234..53.13", "5133.34.4.", "3...4.5213", "442133.311", "1131.14..3", "1223335..3", "4311..431."}

    7

    5

    1000000000

    Returns: 17591

  27. {"..", ".."}

    0

    1

    705418669

    Returns: 0

  28. {".14343", "1..444", "...144", "314..5", "411...", "41.34."}

    4

    5

    955465942

    Returns: 6501

  29. {"..4.", "..5.", "....", "451."}

    1

    2

    509390050

    Returns: 0

  30. {".115", "1.21", "55.1", "1.1."}

    1

    0

    62469818

    Returns: 533438

  31. {"..", "1."}

    0

    1

    469301324

    Returns: 0

  32. {".4..45.4..", "2...5....5", "54....21..", "..........", "52...5.4..", "....5...5.", "2...12...4", ".........2", "45.5......", "..5..25.1."}

    4

    9

    839100924

    Returns: 677037

  33. {"..1.2.5224", "....2.424.", "....5..1.4", "24......44", ".1.....422", "11215.2.24", "224.1...14", "...5.11.2.", ".1.4522...", ".14.41..1."}

    9

    6

    857828350

    Returns: 615310

  34. {"..54..1.", "..4.....", "25..5..1", "4.5.1...", "43.5.5..", "...1...3", "233....4", "....15.."}

    6

    1

    467040551

    Returns: 553460

  35. {"...3...", "...4.23", ".3.341.", "2.5.322", "41...2.", ".3..2.4", "5...5.."}

    0

    2

    429694752

    Returns: 912487

  36. {".124244412", "2.13112332", "24.4244242", "211.442341", "4131.41442", "22112.2131", "113444.314", "421.141.34", "24422143.2", "222324231."}

    8

    6

    435788070

    Returns: 924990

  37. {".141311442", "5.11114134", "53.3111.13", "135.113343", "1525.14111", "11134.4111", "431141.132", "134211..3.", "24543113..", "551314.3.."}

    4

    6

    978736891

    Returns: 295205

  38. {".32245", "3..355", "35.3..", "235.55", "5525.3", ".3344."}

    4

    2

    770910860

    Returns: 902442

  39. {".55..1", "5.25.1", ".4.5..", "112.35", "11.1.1", "4151.."}

    0

    3

    373324323

    Returns: 324319

  40. {"....", "...3", "...3", "...."}

    1

    2

    396953258

    Returns: 0

  41. {"..4.4", "1.441", "4....", ".3...", "..1.."}

    1

    2

    749302373

    Returns: 6967

  42. {".......4", "....3...", "...3.3..", ".45..34.", "......35", "....1...", ".34.....", ".313.4.."}

    3

    2

    122914891

    Returns: 427558

  43. {"..", ".."}

    1

    0

    590473032

    Returns: 0

  44. {".23.5431", "4..4.3.3", "55.4343.", "522.4...", "4532..4.", "3425..32", "33.3.2..", "55.333.."}

    7

    3

    30995198

    Returns: 332569

  45. {".......", "5..5...", "4..55..", ".....4.", "......4", ".2.5..4", "...2..."}

    0

    1

    353740246

    Returns: 0

  46. {".1", ".."}

    0

    1

    826336998

    Returns: 0

  47. {"..5..", ".....", ".....", ".....", "4...."}

    4

    0

    1000000000

    Returns: 0

  48. {".1532555", "5.133123", "55.11111", "51..1514", "551..154", "54.43.45", "132351.3", "5542215."}

    0

    6

    1000000000

    Returns: 831163

  49. {"...", "...", ".1."}

    0

    1

    1000000000

    Returns: 0

  50. {".334", "..4.", ".3..", ".44."}

    1

    0

    1000000000

    Returns: 0

  51. {".3", "1."}

    1

    0

    1000000000

    Returns: 0

  52. {".1.1...243", "1.313..432", "4..3.23422", "34..322.44", "2.3..1.5.3", "33.43.4332", "334.31...1", "3.32232..4", "..33.441.1", "..3113343."}

    0

    6

    1000000000

    Returns: 944294

  53. {".5.", "..3", "3.."}

    0

    1

    1000000000

    Returns: 0

  54. {".1", ".."}

    1

    0

    1000000000

    Returns: 0

  55. {"...", "...", "4.."}

    1

    0

    1000000000

    Returns: 0

  56. {".335", "1.33", "53.4", "455."}

    2

    3

    1000000000

    Returns: 999224

  57. {"..5.4.544.", "5..54.5..5", "....245.5.", ".45.....1.", "425..5.5.5", ".453..445.", ".5445.....", "5....2..45", "4444...4.4", ".41..54.5."}

    2

    5

    1000000000

    Returns: 949395

  58. {".1.5411435", "1...14.451", "54.441.454", "5.3.35.3.5", "4311.4.55.", "514.3.1541", ".51121.14.", "4551144..3", "15555.31.4", "54.5.1121."}

    5

    1

    1000000000

    Returns: 901401

  59. {".5.2......", "4.5555.1..", ".1..43.1..", "24...1..2.", ".1.5...4.4", "2.1....222", "..........", "14.4.....4", "..221.23..", ".42...452."}

    2

    0

    1000000000

    Returns: 595392

  60. {".545.....5", ".....54..3", ".4...4..1.", ".....44..1", "..3...1.4.", "..4.4.432.", "3.23......", ".1.3.32..1", ".14.......", "4.2....13."}

    1

    0

    1000000000

    Returns: 625312

  61. {".4444.4443", "3.14135113", "44.2351442", "141.23.321", "4433.21325", "11331.1512", "243113.151", "4.11451..5", "1422.131.3", "155445.31."}

    7

    0

    1000000000

    Returns: 212872

  62. {"..5.352.2.", "2.55244444", "5..42.11.5", "25..4444.2", "55...2.244", "5.211...25", "2252.4..4.", ".445.43.5.", "242.5242.2", ".244.2..2."}

    1

    4

    536870912

    Returns: 581219

  63. {".14434..52", "4.34414445", "4..35.5551", ".34.125312", "4.5..243.3", ".1.1..5444", "5515.2.254", "355.213.35", "44.24341.5", "1511151.1."}

    4

    2

    536870912

    Returns: 898087

  64. {".....5....", "...3.5...3", "..........", ".........3", ".3......3.", ".35......4", ".........5", "....35....", "..........", ".4........"}

    9

    1

    536870912

    Returns: 582915

  65. {"..31111222", "4.4..12232", "24.2...2..", ".43.41.44.", "2424...52.", ".22.1..422", "23..1...11", "31.1....42", "..3.1113.1", "1.12.2444."}

    3

    0

    536870912

    Returns: 894234

  66. {"..........", "..2.......", "1..3.....1", "1........3", ".....3....", ".5........", ".3........", "......5...", "..........", ".........."}

    4

    7

    536870912

    Returns: 0

  67. {".115525222", "2.5.2.2525", "55...3255.", ".22.2...44", "5422.42245", "41.2..4524", "224251.442", "225525..45", ".5354422.3", ".24...545."}

    3

    6

    536870912

    Returns: 931746

  68. {"....", "....", ".1..", ".2.."}

    1

    0

    2

    Returns: 0

  69. {".41", "1.3", "12."}

    0

    1

    8

    Returns: 4

  70. {".1.223", "..3215", "43.152", "125.51", "2224.2", "11132."}

    2

    3

    8

    Returns: 85

  71. {".4.5..3452", "4..4444.4.", ".......31.", "55..213.4.", "23.3...225", ".53...5.14", ".54.35.4.5", ".1...4..41", "..1.24.5..", "5..144524."}

    8

    4

    5

    Returns: 0

  72. {".235..33", "3.2..4.5", "14.341.5", "35..444.", "45.....5", "35541..5", ".55.1...", "413.41.."}

    1

    6

    8

    Returns: 0

  73. {"......", "......", "......", "......", "..1...", "......"}

    2

    1

    7

    Returns: 0

  74. {"..451.4..3", "...1..4.21", ".3...1.22.", ".13..52.1.", "..52.4.15.", ".2.2..5.1.", "...22...5.", "..14......", "11.1..5..3", ".5..11..5."}

    4

    1

    9

    Returns: 107

  75. {".3222", "..424", "25.23", "325.3", "3345."}

    4

    2

    2

    Returns: 0

  76. {"..", ".."}

    0

    1

    2

    Returns: 0

  77. {"..21.235.1", "3.35155555", "23.4332.43", "55..54.342", "3425.32313", "12453.1434", "323354.323", ".55554..43", "32242334.1", "523324.13."}

    5

    6

    7

    Returns: 23

  78. {".424.42.", "......2.", "2...14.4", "4.2.4.1.", "4242.2.1", "...41..4", "1..1.2.2", "..4422.."}

    6

    7

    3

    Returns: 0

  79. {".3541141", "3.113.33", "33.53443", "1....1.3", "4551....", "31335.4.", "311315.1", "4131144."}

    5

    0

    4

    Returns: 2

  80. {".5.2", "5..5", "...3", ".35."}

    3

    0

    6

    Returns: 0

  81. {".233333", "3.33334", "21.3333", "2.3.323", "233..3.", "43333.3", ".32323."}

    5

    4

    7

    Returns: 2

  82. {".55.13", "3.5..3", "34....", "2....1", "4.33..", ".5.3.."}

    1

    5

    3

    Returns: 1

  83. {".55.....", "........", "5..1....", "....4.4.", "........", "........", "..4524.1", ".1...4.."}

    1

    5

    8

    Returns: 0

  84. {".2....2", "...5...", ".5..5..", "4.....5", ".4....4", ".4.....", ".4....."}

    4

    6

    4

    Returns: 1

  85. {"...", "5..", "25."}

    0

    2

    4

    Returns: 0

  86. {".35235", "...1..", "....25", "53....", ".23...", "..2.1."}

    5

    4

    7

    Returns: 0

  87. {".3", "3."}

    0

    1

    9

    Returns: 1

  88. {"......3..", "...5.....", "....33..3", "5...5..4.", "..35..55.", ".34.....3", "3...4....", "..3.....3", "........."}

    3

    7

    4

    Returns: 1

  89. {".5.", "1..", ".5."}

    1

    0

    1

    Returns: 1

  90. {"..3....", "...4...", ".1....3", ".......", ".......", "...1...", "..414.."}

    2

    1

    1

    Returns: 1

  91. {".3.1..53.3", "1...3.51.5", ".5.33..21.", "544...44.2", "5.54.12.4.", "2..4..51..", ".44.51..15", ".2224.4...", "11.21.....", ".52.1.5..."}

    4

    5

    2

    Returns: 0

  92. {"...14....1", "......13..", ".2...4....", "....52.5..", "1.3..4....", ".3....35.5", "4......1.1", "..4.4.1.54", "....4.11.5", "31144.2.4." }

    7

    2

    1000000000

    Returns: 882571

  93. {".111111111", "1.11111111", "11.1111111", "111.111111", "1111.11111", "11111.1111", "111111.111", "1111111.11", "11111111.1", "111111111." }

    1

    9

    1000000000

    Returns: 604353

  94. {"...14....1", "......13..", ".2...4....", "....52.5..", "1.3..4....", ".3....35.5", "4......1.1", "..4.4.1.54", "....4.11.5", "31144.2.4." }

    7

    2

    999999996

    Returns: 513279

  95. {".555555555", "5.55555555", "55.5554555", "555.555555", "5555.55555", "55555.5555", "555555.555", "5555555.55", "55553555.5", "555555555." }

    0

    7

    1000000000

    Returns: 255218

  96. {".235155443", "5.11232213", "32.2534332", "241.322453", "3515.42344", "52244.3533", "354254.211", "3421354.21", "15112244.5", "455212224." }

    5

    7

    1000000000

    Returns: 321940

  97. {".111411111", "1..1111311", "12.1141111", "111.521511", "1131.41111", "13111.3525", "411111.111", "..4.4.1.54", "111.4111.5", "31144.214." }

    1

    6

    1000000000

    Returns: 651894

  98. {".555555555", "5.55555555", "55.5555555", "555.555555", "5555.55555", "55555.5555", "555555.555", "5555555.55", "55555555.5", "555555555." }

    0

    9

    1000000000

    Returns: 918286

  99. {".111121111", "1.11111111", "11.1111111", "111.111111", "1111.11111", "11211.1111", "111111.111", "1113111.11", "11111111.1", "111111111." }

    0

    9

    1000000000

    Returns: 824117

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: